<p><strong>Lemma 1.</strong> <em>The problem is strongly NP-hard.</em></p>
<p><em>Proof.</em> The proof is by reduction from the NP-hard <a href="https://en.wikipedia.org/wiki/Approximate_max-flow_min-cut_theorem#Sparsest_cuts" rel="nofollow noreferrer">Sparsest Cut</a> problem.  For this problem,
the input is a connected undirected graph <span class="math-container">$G=(V, E)$</span> and a budget <span class="math-container">$\lambda &gt; 0$</span>.  The problem is to determine
whether there is a non-trivial cut <span class="math-container">$(S, \overline S)$</span>
(where <span class="math-container">$S\subset V$</span> and <span class="math-container">$\overline S = V\setminus S \subset V$</span>)
such that <span class="math-container">$\phi(S) \le \lambda$</span> where
<span class="math-container">$$
\phi(S) \stackrel{\textsf{def}}{=} \frac{|E \cap (S \times \overline S)|}{|S| \times |\overline S|}.~~~~~~~(1)$$</span></p>
<ol>
<li><p>For any cut <span class="math-container">$S$</span>, the numerator and denominator in <span class="math-container">$\phi(S)$</span> are integers in <span class="math-container">$[n^2]$</span>.</p>
</li>
<li><p>So <span class="math-container">$\phi(S) \in U \stackrel{\text{def}}= \{i/j : i, j \in [n^2]\}$</span>.</p>
</li>
<li><p>So, fixing <span class="math-container">$i'/j' = \min\{i/j \in U : i/j &gt; \lambda\}$</span>,
we have <span class="math-container">$\phi(S) \le \lambda$</span> iff <span class="math-container">$\phi(S) &lt; i'/j'$</span>.</p>
</li>
<li><p>So Condition (1) in the definition of Sparsest Cut is equivalent to
<span class="math-container">$$
\frac{|E \cap (S \times \overline S)|}{|S| \times |\overline S|}
&lt; \frac{i'}{j'}.~~~~~~~(2)$$</span></p>
</li>
<li><p>Rewriting (using <span class="math-container">$|S|\times |\overline S| \ge 0$</span>), Condition (2) is equivalent to
<span class="math-container">$$
i' |S| \times |\overline S| - j' |E \cap (S \times \overline S)|
&gt; 0. ~~~~~(3)$$</span></p>
</li>
<li><p>Hence, the instance <span class="math-container">$(G=(V,E), \lambda)$</span> of Sparsest Cut
can be reduced to an instance <span class="math-container">$G'=(V, E')$</span> of OP's problem
where <span class="math-container">$G'$</span> is obtained from <span class="math-container">$G$</span> as follows:
give each edge <span class="math-container">$e\in E$</span> weight <span class="math-container">$i' - j'$</span>,
and, for each unordered pair <span class="math-container">$(u, w)$</span> of vertices that is not an edge,
add an edge of weight <span class="math-container">$i'$</span>.</p>
</li>
<li><p>Then, for any cut <span class="math-container">$(S, \overline S)$</span>,
the total weight of the edges crossing the cut in <span class="math-container">$G'$</span>
equals the left-hand side of (3),
so is positive iff the cut meets Condition (1).
Hence, <span class="math-container">$G$</span> has a sufficiently sparse cut
iff <span class="math-container">$G'$</span> has a cut with positive total weight.
Hence the reduction is correct.</p>
</li>
<li><p>The reduction can be implemented in polynomial time,
and produces instances whose weights are quadratic in <span class="math-container">$n$</span>.
Lemma 1 follows. <span class="math-container">$~~~~\Box$</span></p>
</li>
</ol>

CC BY-SA 4.0
2024-04-20T13:13:26.837Z
The problem remains NP-hard if restricted to bipartite graphs with edge weights in $\{-1, 1\}$.  See https://cstheory.stackexchange.com/a/54213/8237 .
Neal Young
CC BY-SA 4.0
2024-04-24T11:38:52.203Z
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'$.
badboul
CC BY-SA 4.0
2024-04-19T03:26:40.507Z
2024-04-24T11:55:08.873Z
2024-04-24T11:55:08.873Z
Neal Young
<p>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:</p>
<p>Given a graph <span class="math-container">$G=(V, E)$</span> and edge weights <span class="math-container">$w: E \to \mathbb{R}$</span> does there exists <span class="math-container">$S \subseteq V$</span> such that <span class="math-container">$\sum_{e \in \delta(S)} w(e) &gt; 0$</span> where <span class="math-container">$\delta(S)$</span> is the set of edges with exactly one node in <span class="math-container">$S$</span>.</p>
<p>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).</p>
<p>There is another question about the hardness of approximating this problem and <a href="https://cstheory.stackexchange.com/a/2318/64993">this</a> 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.</p>
<p>The comments to <a href="https://cstheory.stackexchange.com/q/36955/64993">this</a> question and <a href="https://cstheory.stackexchange.com/a/50325/64993">this</a> 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.</p>

<approximation-hardness><np-complete><max-cut>
Deciding if max-cut with negative edge weights has a solution with positive value
badboul
# Deciding if max-cut with negative edge weights has a solution with positive value

(Asked by: username_0 on 2024-04-18)

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](https://cstheory.stackexchange.com/a/2318/64993) 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](https://cstheory.stackexchange.com/q/36955/64993) question and [this](https://cstheory.stackexchange.com/a/50325/64993) 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.

**Tags:** approximation-hardness, np-complete, max-cut


---

## 1 answers

### Answer by username_1 on 2024-04-19. Score: 2 | Accepted answer

**Lemma 1.** *The problem is strongly NP-hard.*

*Proof.* The proof is by reduction from the NP-hard [Sparsest Cut](https://en.wikipedia.org/wiki/Approximate_max-flow_min-cut_theorem#Sparsest_cuts) 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$

> **Comments:**
> **username_1**: The problem remains NP-hard if restricted to bipartite graphs with edge weights in $\{-1, 1\}$.  See https://cstheory.stackexchange.com/a/54213/8237 .  
> **username_0**: 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'$.  

---

