9
$\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)?

$\endgroup$
13
  • 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$ Nov 11, 2016 at 9:22
  • 2
    $\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$ 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$ Nov 11, 2016 at 23:30
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 17, 2016 at 15:38
  • 1
    $\begingroup$ (i) @SashoNikolov, yes, also if the graph is bipartite (as specified) one can simply take the bipartition and get weight equal to the total weight. (ii)Without the restrictions to bipartite graphs and weights in $\{-1,1\}$, the problem seems to be NP-hard (cstheory.stackexchange.com/a/54210/8237). $\endgroup$
    – Neal Young
    Apr 19 at 3:38

1 Answer 1

0
$\begingroup$

Theorem 1. The problem is NP-hard.

The proof is by reduction from the NP-hard Sparsest Cut problem. For Sparsest Cut, the input is a connected undirected graph $G=(V, E)$ and a budget $\lambda > 0$. The problem is to determine whether there is a non-trivial cut $(S, \overline S)$, where $\overline S = V\setminus S$, such that $\phi(S) \le \lambda$, where $$ \phi(S) \stackrel{\text{def}}{=} \frac{|E \cap (S \times \overline S)|}{|S| \times |\overline S|}.$$

Proof sketch. We adapt a previous proof that Sparsest Cut (in general graphs) reduces to the problem of finding a positive cut in a graph with (possibly negative) edge weights. There are two new challenges: the reduction must produce a graph that (i) has edge weights in $\{-1,1\}$, and (ii) is bipartite. We give a reduction via the following intermediary problems:

  • Define $C$ to be the problem of determining whether a given graph with (possibly negative) integer edge weights has a positive cut.

  • Define $C_{\le 1}$ to be $C$ restricted to instances with maximum edge weight 1.

  • Define $B_{\le 1}$ to be $C_{\le 1}$ restricted to bipartite graphs.

  • Define $B_{-1,1}$ to be $B_{\le 1}$ restricted to instances with edge weights in $\{-1, 1\}$.

Note that $B_{-1,1}$ is OP's problem.


Lemma 1. $C$ is strongly NP-hard.

Proof sketch. By reduction from Sparsest Cut. Fix a Sparsest Cut instance $G=(V, E)$.

  1. For any cut $S$, the numerator and denominator in $\phi(S)$ are integers in $[n^2]$.

  2. So $\phi(S) \in U \stackrel{\text{def}}= \{i/j : i, j \in [n^2]\}$.

  3. So, fixing $i'/j' = \min\{i/j \in U : i/j > \lambda\}$, we have $\phi(S) \le \lambda$ iff $\phi(S) < i'/j'$.

  4. So Condition (1) in the definition of Sparsest Cut is equivalent to $$ \frac{|E \cap (S \times \overline S)|}{|S| \times |\overline S|} < \frac{i'}{j'}.~~~~~~~(2)$$

  5. Rewriting (using $|S|\times |\overline S| \ge 0$), Condition (2) is equivalent to $$ i' |S| \times |\overline S| - j' |E \cap (S \times \overline S)| > 0. ~~~~~(3)$$

  6. Hence, the instance $(G=(V,E), \lambda)$ of Sparsest Cut can be reduced to an instance $G'=(V, E')$ of $C$ where $G'$ is obtained from $G$ as follows: give each edge $e\in E$ weight $i' - j'$, and, for each unordered pair $(u, w)$ of vertices that is not an edge, add an edge of weight $i'$.

  7. Then, for any cut $(S, \overline S)$, the total weight of the edges crossing the cut in $G'$ equals the left-hand side of (3), so is positive iff the cut meets Condition (1). Hence, $G$ has a sufficiently sparse cut iff $G'$ has a cut with positive total weight. Hence the reduction is correct.

  8. The reduction can be implemented in polynomial time, and produces instances whose weights are quadratic in $n$. Lemma 1 follows. $~~~~\Box$


Lemma 2. $C_{\le 1}$ is strongly NP-hard.

Proof sketch. By reduction from $C$ (restricted to polynomially bounded integer edge weights).

Let graph $G=(V, E)$ be an instance of the latter problem. Let $w_{\max}$ be the maximum edge weight. Given $G$, the reduction outputs the graph $G'=(V', E')$, with maximum edge weight $1$, obtained from $G$ as follows.

  1. for each edge $e=(v, v')\in E$ with weight $w(v, v') \ge 2$:
  2. $~~~~$ delete the edge and replace it with $w(v, v')$ new length-2 paths $(v, \alpha_{ei}, v')$ for $i\in [w(v, v')]$, using $w(v, v')$ new intermediate vertices $\{\alpha_{ei} : i\in [w(v, v')]\}$
  3. $~~~$ give each of the $w(v, v')$ new edges $(v, \alpha_{ei})$ weight $-|E| w_{\max}$
  4. $~~~$ give each of the $w(v, v')$ new edges $(\alpha_{ei}, v')$ weight $1$
  1. To see that the reduction is correct, note that any positive-weight cut $(S', \overline S')$ in $G'$ has the following property: for any original edge $e=(v, v')$ replaced by paths in the reduction, none of the edges $(v, \alpha_{ei})$ (for $i\in [-w(v, v')]$) crosses the cut $(S', \overline S')$ (as otherwise the cut is crossed by an edge of weight $-|E| w_{\max}$, so has total weight at most $|E| w_{\max} - |E| w_{\max} = 0$).

  2. Cuts with the above property correspond to cuts $(S, \overline S)$ in $G$, where $S$ and $\overline S$ are obtained from $S'$ and $\overline S'$ by contracting all the edges $(v, \alpha_{ei})$ of weight $-|E|w_{\max}$ in $G'$. This correspondence is invertible and preserves cost. So the reduction is correct.

  3. The reduction is poly-time by the assumption that the weights are polynomially bounded integers. This proves Lemma 2. $~~~~\Box$


Lemma 3. $B_{\le 1}$ is strongly NP-hard.

Proof sketch. By reduction from $C_{\le 1}$.

Let graph $G=(V, E)$ be an instance of the latter problem. Given $G$, the reduction outputs the bipartite graph $G'=(X, Y, E')$, with maximum edge weight $1$, obtained from $G$ as follows.

  1. for each vertex $v\in V$:
  2. $~~~$ make two vertices $x_v\in X$ and $y_v\in Y$, and edge $(x_v, y_v)$ in $E'$ of weight $-|E|$
  3. for each edge $e=(u, w)\in E$:
  4. $~~~$ make an edge $(x_v, y_w) \in E'$ with the same weight as $e$

(Step 4 could just as well make edge $(x_w, y_v)$ instead.)

  1. To see that the reduction is correct, note that each positive-weight cut $(S', \overline S')$ in $G'$ has the following property: for any $v\in V$, the edge $(x_v, y_v)$ introduced in Step 1 does not cross the cut (as otherwise the cut would have total weight at most $-|E| + |E| = 0$).

  2. Cuts with the above property correspond to cuts $(S, \overline S)$ in $G$, where $S$ and $\overline S$ are obtained from $S'$ and $\overline S'$ by contracting all the edges $(x_v, y_v)$ of weight $-|E|$ in $G'$.

  3. This correspondence is invertible and preserves cost. So the reduction is correct.

  4. It can be implemented in polynomial time, and produces a bipartite graph with polynomially bounded edge weights (and max edge weight 1). This proves Lemma 3. $~~~~\Box$


The next lemma completes the proof of Theorem 1.

Lemma 4. $B_{-1,1}$ is NP-hard.

Proof sketch. By reduction from $B_{\le 1}$.

Fix any instance $G=(X, Y, E)$ of the latter problem. Assume WLOG that $G$ has no edges of weight zero (otherwise simply delete them). Given $G$, the reduction outputs the bipartite graph $G'=(X', Y', E')$ with edge weights in $\{-1, 1\}$ obtained from $G$ as follows.

  1. For each edge $e=(v, v')\in E$ with weight $w(v, v') \not\in\{-1, 1\}$ (so $w(v, v') \le -2$):
  2. $~~~$ delete the edge and replace it with $-w(v, v')$ new length-3 paths $(v, \alpha_{ei}, \beta_{ei}, v')$ for $i\in > [-w(v, v')]$, adding the new "intermediate" vertices $$\{\alpha_{ei} : i\in [-w(v, v')]\} \textsf{ and } \{\beta_{ei} : i\in [-w(v, v')]\}$$ $~~~~$ to $X'$ and $Y'$, respectively
  3. $~~~$ give each of these $-3w(v, v')$ new edges weight -1

(If multi-edges were allowed, we would not need the intermediate vertices.)

  1. To see that the reduction is correct, note that, in considering positive-weight cuts $(S', \overline S')$ in $G'$, we can restrict to those with the following properties: for any original edge $e=(v, v')$ replaced by paths in the reduction, if $v$ and $v'$ are on the same side of the cut, then all intermediate vertices $\alpha_{ei}$ and $\beta_{ei}$ (for $i\in [-w(v, v')]$) are also in that side; if $v$ and $v'$ are on opposite sides, then each $\alpha_{ei}$ is on the side with $v$, and each $\beta_{ei}$ is on the side with $v'$ (as otherwise making it so does not decrease the cut cost).

  2. Cuts with the above property correspond to cuts $(S, \overline S)$ in $G$, where $S$ and $\overline S$ are obtained from $S'$ and $\overline S'$ by restricting to vertices in $G$.

  3. This correspondence is invertible and preserves cost. So the reduction is correct.

  4. The reduction produces a bipartite graph with edge weights in $\{-1, 1\}$ and can be implemented in poly-time by the assumption that the weights in $G$ are polynomially bounded. This proves Lemma 4, and Theorem 1. $~~~~\Box$


$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.