7

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

Community
  • 1
curl-up
  • 71
  • 3
  • 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. – Sasho Nikolov Nov 11 '16 at 01:03
  • Shouldnt this be in P. There is a linear program that solves it. – S. Pek Nov 11 '16 at 01:36
  • @S.Pek what is the linear program? – Sasho Nikolov Nov 11 '16 at 03:12
  • We consider the linear program for minimum cut, then add the constraint the the minimum cut should be positive. – S. Pek Nov 11 '16 at 03:20
  • 2
    @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. – Sasho Nikolov Nov 11 '16 at 09:22
  • I have edited the question. If needed, we can presume that the total sum of weights is non-negative, and that such cut exists. The problem then remains to find it. – curl-up Nov 11 '16 at 22:21
  • 1
    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.) – Sasho Nikolov Nov 11 '16 at 22:56
  • Thanks! Could you please point me to some reference on this?

    What if we know that the solution exists, but the total sum of weights is negative (this would probably be my primary question, but I'm exploring different options)?

     – curl-up Nov 11 '16 at 23:08
  • 1
    You can see for example http://www.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}$. – Sasho Nikolov Nov 11 '16 at 23:30
  • @SashoNikolov, what if the sum of weights is zero (hence non-negative)? Do you think the greedy algorithm necessarily finds a positive-weight cut? – Neal Young Nov 16 '16 at 21:58
  • @NealYoung Oh..no I am not claiming that. I was being sloppy with non-negative vs positive weight. All I am claiming is that the greedy algorithm finds a cut of weight at least the total weighted divided by 2. – Sasho Nikolov Nov 17 '16 at 15:38

0 Answers0