<p><strong>Theorem 1.</strong> <em>The problem is NP-hard.</em></p>
<p>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 Sparsest Cut,
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">$\overline S = V\setminus S$</span>,
such that <span class="math-container">$\phi(S) \le \lambda$</span>, where
<span class="math-container">$$
\phi(S) \stackrel{\text{def}}{=} \frac{|E \cap (S \times \overline S)|}{|S| \times |\overline S|}.$$</span></p>
<p><em>Proof sketch.</em>
We adapt <a href="https://cstheory.stackexchange.com/a/54210/8237">a previous proof</a>
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
<span class="math-container">$\{-1,1\}$</span>,
and (ii) is bipartite.
We give a reduction via the following intermediary problems:</p>
<ul>
<li><p>Define <span class="math-container">$C$</span> to be the problem of determining whether a given graph with (possibly negative) integer edge weights has a positive cut.</p>
</li>
<li><p>Define <span class="math-container">$C_{\le 1}$</span> to be <span class="math-container">$C$</span> restricted to instances with maximum edge weight 1.</p>
</li>
<li><p>Define <span class="math-container">$B_{\le 1}$</span> to be <span class="math-container">$C_{\le 1}$</span> restricted to bipartite graphs.</p>
</li>
<li><p>Define <span class="math-container">$B_{-1,1}$</span> to be <span class="math-container">$B_{\le 1}$</span> restricted to instances with edge weights in <span class="math-container">$\{-1, 1\}$</span>.</p>
</li>
</ul>
<p>Note that <span class="math-container">$B_{-1,1}$</span> is OP's problem.</p>
<hr />
<p><strong>Lemma 1.</strong> <em><span class="math-container">$C$</span> is strongly NP-hard.</em></p>
<p><em>Proof sketch.</em>  By reduction from Sparsest Cut.
Fix a Sparsest Cut instance <span class="math-container">$G=(V, E)$</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 <span class="math-container">$C$</span>
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>
<hr />
<p><strong>Lemma 2.</strong> <em><span class="math-container">$C_{\le 1}$</span> is strongly NP-hard.</em></p>
<p><em>Proof sketch.</em>  By reduction from <span class="math-container">$C$</span> (restricted to polynomially bounded integer edge weights).</p>
<p>Let graph <span class="math-container">$G=(V, E)$</span> be an instance of the latter problem.
Let <span class="math-container">$w_{\max}$</span> be the maximum edge weight.
Given <span class="math-container">$G$</span>, the reduction outputs the graph <span class="math-container">$G'=(V', E')$</span>,
with maximum edge weight <span class="math-container">$1$</span>, obtained from <span class="math-container">$G$</span> as follows.</p>
<blockquote>
<ol>
<li>for each edge <span class="math-container">$e=(v, v')\in E$</span> with weight <span class="math-container">$w(v, v') \ge 2$</span>:</li>
<li><span class="math-container">$~~~~$</span> delete the edge and replace it with <span class="math-container">$w(v, v')$</span> new length-2 paths <span class="math-container">$(v, \alpha_{ei}, v')$</span> for <span class="math-container">$i\in [w(v, v')]$</span>, using <span class="math-container">$w(v, v')$</span> new intermediate vertices <span class="math-container">$\{\alpha_{ei} : i\in [w(v, v')]\}$</span></li>
<li><span class="math-container">$~~~$</span> give each
of the <span class="math-container">$w(v, v')$</span> new edges <span class="math-container">$(v, \alpha_{ei})$</span> weight <span class="math-container">$-|E| w_{\max}$</span></li>
<li><span class="math-container">$~~~$</span> give each of the <span class="math-container">$w(v, v')$</span> new edges <span class="math-container">$(\alpha_{ei}, v')$</span> weight <span class="math-container">$1$</span></li>
</ol>
</blockquote>
<ol>
<li><p>To see that the reduction is correct,
note that any positive-weight cut
<span class="math-container">$(S', \overline S')$</span> in <span class="math-container">$G'$</span>
has the following property:
<em>for any original edge <span class="math-container">$e=(v, v')$</span> replaced by paths in the reduction,
none of the edges <span class="math-container">$(v, \alpha_{ei})$</span> (for <span class="math-container">$i\in [-w(v, v')]$</span>)
crosses the cut <span class="math-container">$(S', \overline S')$</span></em>
(as otherwise the cut is crossed by an edge of weight
<span class="math-container">$-|E| w_{\max}$</span>,
so has total weight at most <span class="math-container">$|E| w_{\max} - |E| w_{\max} = 0$</span>).</p>
</li>
<li><p>Cuts with the above property correspond to cuts
<span class="math-container">$(S, \overline S)$</span> in <span class="math-container">$G$</span>,
where <span class="math-container">$S$</span> and <span class="math-container">$\overline S$</span> are obtained from <span class="math-container">$S'$</span> and <span class="math-container">$\overline S'$</span> by contracting all the edges <span class="math-container">$(v, \alpha_{ei})$</span> of weight <span class="math-container">$-|E|w_{\max}$</span>
in <span class="math-container">$G'$</span>.
This correspondence is invertible and preserves cost.
So the reduction is correct.</p>
</li>
<li><p>The reduction is poly-time by the assumption that
the weights are polynomially bounded integers.
This proves Lemma 2. <span class="math-container">$~~~~\Box$</span></p>
</li>
</ol>
<hr />
<p><strong>Lemma 3.</strong> <em><span class="math-container">$B_{\le 1}$</span> is strongly NP-hard.</em></p>
<p><em>Proof sketch.</em>  By reduction from <span class="math-container">$C_{\le 1}$</span>.</p>
<p>Let graph <span class="math-container">$G=(V, E)$</span> be an instance of the latter problem.
Given <span class="math-container">$G$</span>, the reduction outputs the bipartite graph <span class="math-container">$G'=(X, Y, E')$</span>,
with maximum edge weight <span class="math-container">$1$</span>, obtained from <span class="math-container">$G$</span> as follows.</p>
<blockquote>
<ol>
<li>for each vertex <span class="math-container">$v\in V$</span>:</li>
<li><span class="math-container">$~~~$</span> make two vertices <span class="math-container">$x_v\in X$</span> and <span class="math-container">$y_v\in Y$</span>, and edge <span class="math-container">$(x_v, y_v)$</span> in <span class="math-container">$E'$</span> of weight <span class="math-container">$-|E|$</span></li>
<li>for each edge <span class="math-container">$e=(u, w)\in E$</span>:</li>
<li><span class="math-container">$~~~$</span> make an edge <span class="math-container">$(x_v, y_w) \in E'$</span> with the same weight as <span class="math-container">$e$</span></li>
</ol>
</blockquote>
<p>(Step 4 could just as well make edge <span class="math-container">$(x_w, y_v)$</span> instead.)</p>
<ol>
<li><p>To see that the reduction is correct,
note that each positive-weight cut
<span class="math-container">$(S', \overline S')$</span> in <span class="math-container">$G'$</span>
has the following property:
<em>for any <span class="math-container">$v\in V$</span>, the edge <span class="math-container">$(x_v, y_v)$</span> introduced in Step 1
does not cross the cut</em>
(as otherwise the cut would have total weight at most
<span class="math-container">$-|E| + |E| = 0$</span>).</p>
</li>
<li><p>Cuts with the above property correspond to cuts
<span class="math-container">$(S, \overline S)$</span> in <span class="math-container">$G$</span>,
where <span class="math-container">$S$</span> and <span class="math-container">$\overline S$</span> are obtained from <span class="math-container">$S'$</span> and <span class="math-container">$\overline S'$</span> by contracting all the edges <span class="math-container">$(x_v, y_v)$</span> of weight <span class="math-container">$-|E|$</span>
in <span class="math-container">$G'$</span>.</p>
</li>
<li><p>This correspondence is invertible and preserves cost.
So the reduction is correct.</p>
</li>
<li><p>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. <span class="math-container">$~~~~\Box$</span></p>
</li>
</ol>
<hr />
<p>The next lemma completes the proof of Theorem 1.</p>
<p><strong>Lemma 4.</strong> <em><span class="math-container">$B_{-1,1}$</span> is NP-hard.</em></p>
<p><em>Proof sketch.</em>  By reduction from <span class="math-container">$B_{\le 1}$</span>.</p>
<p>Fix any instance <span class="math-container">$G=(X, Y, E)$</span> of the latter problem.
Assume WLOG that <span class="math-container">$G$</span> has no edges of weight zero
(otherwise simply delete them).
Given <span class="math-container">$G$</span>, the reduction outputs the bipartite graph <span class="math-container">$G'=(X', Y', E')$</span>
with edge weights in <span class="math-container">$\{-1, 1\}$</span> obtained from <span class="math-container">$G$</span> as follows.</p>
<blockquote>
<ol>
<li>For each edge <span class="math-container">$e=(v, v')\in E$</span> with weight <span class="math-container">$w(v, v') \not\in\{-1, 1\}$</span> (so <span class="math-container">$w(v, v') \le -2$</span>):</li>
<li><span class="math-container">$~~~$</span> delete the edge and replace it with <span class="math-container">$-w(v, v')$</span> new length-3 paths <span class="math-container">$(v, \alpha_{ei}, \beta_{ei}, v')$</span> for <span class="math-container">$i\in
&gt; [-w(v, v')]$</span>, adding the new &quot;intermediate&quot; vertices
<span class="math-container">$$\{\alpha_{ei} : i\in [-w(v, v')]\} \textsf{ and } \{\beta_{ei} : i\in [-w(v, v')]\}$$</span>
<span class="math-container">$~~~~$</span> to <span class="math-container">$X'$</span> and <span class="math-container">$Y'$</span>, respectively</li>
<li><span class="math-container">$~~~$</span> give each of these <span class="math-container">$-3w(v, v')$</span> new edges weight -1</li>
</ol>
</blockquote>
<p>(If multi-edges were allowed, we would not need the intermediate vertices.)</p>
<ol>
<li><p>To see that the reduction is correct,
note that, in considering positive-weight cuts
<span class="math-container">$(S', \overline S')$</span> in <span class="math-container">$G'$</span>,
we can restrict to those with the following properties:
<em>for any original edge <span class="math-container">$e=(v, v')$</span> replaced by paths in the reduction,
if <span class="math-container">$v$</span> and <span class="math-container">$v'$</span> are on the same side of the cut,
then all intermediate vertices <span class="math-container">$\alpha_{ei}$</span>
and <span class="math-container">$\beta_{ei}$</span> (for <span class="math-container">$i\in [-w(v, v')]$</span>)
are also in that side;
if <span class="math-container">$v$</span> and <span class="math-container">$v'$</span> are on opposite sides,
then each <span class="math-container">$\alpha_{ei}$</span> is on the side with <span class="math-container">$v$</span>,
and each <span class="math-container">$\beta_{ei}$</span> is on the side with <span class="math-container">$v'$</span></em>
(as otherwise making it so does not decrease the cut cost).</p>
</li>
<li><p>Cuts with the above property correspond to cuts
<span class="math-container">$(S, \overline S)$</span> in <span class="math-container">$G$</span>,
where <span class="math-container">$S$</span> and <span class="math-container">$\overline S$</span> are obtained from <span class="math-container">$S'$</span> and <span class="math-container">$\overline S'$</span> by restricting to vertices in <span class="math-container">$G$</span>.</p>
</li>
<li><p>This correspondence is invertible and preserves cost.
So the reduction is correct.</p>
</li>
<li><p>The reduction produces a bipartite graph
with edge weights in <span class="math-container">$\{-1, 1\}$</span>
and can be implemented in poly-time by the assumption that
the weights in <span class="math-container">$G$</span> are polynomially bounded.
This proves Lemma 4, and Theorem 1. <span class="math-container">$~~~~\Box$</span></p>
</li>
</ol>
<hr />

CC BY-SA 4.0
2024-04-19T22:11:05.280Z
2024-04-24T11:55:43.793Z
2024-04-24T11:55:43.793Z
Neal Young
<p>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).</p>

<p>If not, is there such an algorithm when two nodes on the opposite sides of such cut are already provided?</p>

<p>I am aware that this might be a duplicate of <a href="https://cstheory.stackexchange.com/questions/2312/max-cut-with-negative-weight-edges">this question</a>. 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)?</p>

CC BY-SA 3.0
2016-11-11T01:03:55.050Z
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
CC BY-SA 3.0
2016-11-11T01:36:51.217Z
Shouldnt this be in P. There is a linear program that solves it.
S. Pek
CC BY-SA 3.0
2016-11-11T03:12:01.910Z
@S.Pek what is the linear program?
Sasho Nikolov
CC BY-SA 3.0
2016-11-11T03:20:28.860Z
We consider the linear program for minimum cut, then add the constraint the the minimum cut should be positive.
S. Pek
CC BY-SA 3.0
2016-11-11T09:22:09.377Z
@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
CC BY-SA 3.0
2016-11-11T22:21:08.967Z
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
CC BY-SA 3.0
2016-11-11T22:56:20.893Z
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
CC BY-SA 3.0
2016-11-11T23:08:54.550Z
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
CC BY-SA 3.0
2016-11-11T23:30:20.300Z
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
CC BY-SA 3.0
2016-11-16T21:58:08.560Z
@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
CC BY-SA 3.0
2016-11-17T15:38:39.443Z
@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
CC BY-SA 4.0
2024-04-19T03:38:29.053Z
(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 (https://cstheory.stackexchange.com/a/54210/8237).
Neal Young
CC BY-SA 4.0
2024-04-23T02:10:10.943Z
@NealYoung that's pretty similar to the proof I had in mind. But I see you also managed to get it to work for $\{-1, 1\}$ weights, that's nice
Sasho Nikolov
<ds.algorithms><graph-theory><approximation-algorithms><max-cut>
Positive cut algorithm on bipartite graphs with negative weights
curl-up
# Positive cut algorithm on bipartite graphs with negative weights

(Asked by: username_0 on 2016-11-10)

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](https://cstheory.stackexchange.com/questions/2312/max-cut-with-negative-weight-edges). 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)?

**Tags:** ds.algorithms, graph-theory, approximation-algorithms, max-cut
> **Comments:**
> **username_1**: 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.  
> **username_2**: Shouldnt this be in P. There is a linear program that solves it.  
> **username_1**: @S.Pek what is the linear program?  
> **username_2**: We consider the linear program for minimum cut, then add the constraint the the minimum cut should be positive.  
> **username_1**: @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.  
> **username_0**: 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.  
> **username_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.)  
> **username_0**: 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)?  
> **username_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\}$.  
> **username_3**: @SashoNikolov, what if the sum of weights is *zero* (hence non-negative)?  Do you think the greedy algorithm necessarily finds a positive-weight cut?  
> **username_1**: @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.  
> **username_3**: (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 (https://cstheory.stackexchange.com/a/54210/8237).  
> **username_1**: @NealYoung that's pretty similar to the proof I had in mind. But I see you also managed to get it to work for $\{-1, 1\}$ weights, that's nice  

---

## 1 answers

### Answer by username_3 on 2024-04-19. Score: 0

**Theorem 1.** *The problem is NP-hard.*

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 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](https://cstheory.stackexchange.com/a/54210/8237)
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$

---


---

