# Finding a cut maximizing average weight of cut edges

Just checking if this version of Max Cut is still NP-hard:

Given a fully connected graph $$G(V,E)$$, where every vertex is connected to every other vertex, and where every edge has a weight associated with it. Find a cut in $$G$$ such that the average weight of the cut edges is maximal. See the example below, where other cuts may result in more edges cut, but not in a higher average weight.

• You can find maximum mean cut in the literature, but this is a directed problem, whose undirected version seems to correspond to the task of minimizing the average cost of a cut edge. – Yuval Filmus Nov 5 '20 at 9:07
• @YuvalFilmus Do you have a reference for the "the task of minimizing the average cost of a cut edge"? I may be able to transform the problem into a min-cut one, given that the edge weights lie in a certain range. – DBrons Nov 5 '20 at 9:43
• google.com/search?q=%22maximum+mean+cut%22 – Yuval Filmus Nov 5 '20 at 9:44