7
$\begingroup$

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)?

Improve this question
$\endgroup$
12
  • $\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, 2016 at 1:03
  • $\begingroup$ Shouldnt this be in P. There is a linear program that solves it. $\endgroup$
    – S. Pek
    Nov 11, 2016 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, 2016 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, 2016 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, 2016 at 23:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.