1
$\begingroup$

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.

enter image description here

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 5 '20 at 9:07
  • $\begingroup$ @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. $\endgroup$ – DBrons Nov 5 '20 at 9:43
  • $\begingroup$ google.com/search?q=%22maximum+mean+cut%22 $\endgroup$ – Yuval Filmus Nov 5 '20 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.