3
$\begingroup$

I am interested in the complexity of the decision problem whether max-cut with positive and negative edge weights has a solution with positive value:

Given a graph $G=(V, E)$ and edge weights $w: E \to \mathbb{R}$ does there exists $S \subseteq V$ such that $\sum_{e \in \delta(S)} w(e) > 0$ where $\delta(S)$ is the set of edges with exactly one node in $S$.

If this decision problem is NP-complete, this would imply that the max-cut problem with positive and negative edge weights cannot be approximated within any factor (in contrast to max-cut with non-negative edge weights).

There is another question about the hardness of approximating this problem and this answer shows that it cannot be approximated within a factor of 2. The two other answers to that question suggest that the problem can be approximated. However, from my understanding these results are for special cases and different variations of this problem.

The comments to this question and this answer to another question claim that the decision problem is NP-complete. However no argument for this claim is provided and I cannot find this statement anywhere else.

$\endgroup$

1 Answer 1

2
$\begingroup$

Lemma 1. The problem is strongly NP-hard.

Proof. The proof is by reduction from the NP-hard Sparsest Cut problem. For this problem, 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 $S\subset V$ and $\overline S = V\setminus S \subset V$) such that $\phi(S) \le \lambda$ where $$ \phi(S) \stackrel{\textsf{def}}{=} \frac{|E \cap (S \times \overline S)|}{|S| \times |\overline S|}.~~~~~~~(1)$$

  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 OP's problem 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$

$\endgroup$
2
  • $\begingroup$ The problem remains NP-hard if restricted to bipartite graphs with edge weights in $\{-1, 1\}$. See cstheory.stackexchange.com/a/54213/8237 . $\endgroup$
    – Neal Young
    Commented Apr 20 at 13:13
  • 1
    $\begingroup$ I think in 6, the the weights of the unordered pairs (u,w) that are not edges of G should have weight $+i'$, not $-j'$. $\endgroup$
    – badboul
    Commented Apr 24 at 11:38

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.