Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If it is needed, we can presume that such cut exists (but sum of all weights may be negative).

If not, is there such an algorithm when two nodes on the opposite sides of such cut are already provided?

I am aware that this might be a duplicate of this question. I went through the given articles, but I am not sure if they answer my question. For example, I do not understand what the approximation performance means in the context of negative weights. If all but one cut have non-positive values, does that mean that the approximation algorithm will find that single positive solution (because only for that solution the performance condition is met)?

  • $\begingroup$ My guess is that detecting whether there is a non-negative cut is NP-hard. I can show this when the weights are in the continuous range $[-1,1]$. The approximation algorithm suggested in the link you refer to works only when the total sum of weights is non-negative, which implies the existence of a non-negative cut. $\endgroup$ – Sasho Nikolov Nov 11 '16 at 1:03
  • $\begingroup$ Shouldnt this be in P. There is a linear program that solves it. $\endgroup$ – S. Pek Nov 11 '16 at 1:36
  • 2
    $\begingroup$ @S.Pek there are many reasons this doesn't work. (1) The question asks about detecting that the max cut is positive, not the min cut. (This is more of a technicality once you allow negative weights though.) (2) All the LP formulations of min cut are integral only with non-negative weights (otherwise you'd be able to solve max cut). (3) Adding even a single constraint to an integral LP can break integrality. $\endgroup$ – Sasho Nikolov Nov 11 '16 at 9:22
  • 1
    $\begingroup$ Then the greedy algorithm that puts each vertex on the side that maximizes the cut value works. (This is also the derandomization of the simple randomized algorithm via the method of conditional expectations.) $\endgroup$ – Sasho Nikolov Nov 11 '16 at 22:56
  • 1
    $\begingroup$ You can see for example cs.cornell.edu/courses/cs783/2003fa/lecture2.ps (algorithm 1.2). If you had an algorithm that always finds a positive cut when one exists, you could use it to solve the decision version of the problem. Like I said above, I believe the decision version should be NP-hard when the total sum of weights is negative. I have a proof for general graphs with weights in $[-1,1]$, but I haven't thought about a proof for bipartite graphs with weights in $\{-1, 1\}$. $\endgroup$ – Sasho Nikolov Nov 11 '16 at 23:30

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.