<p><strong>Theorem 1.</strong> <em>The given problem is NP-hard, by reduction from MAX-CUT.</em></p>
<p><em>Proof.</em> Call the given problem Positive Discrepancy Cut (PDC).  Define <em>weighted PDC</em> to be the generalization where the input is a graph <span class="math-container">$G=(V,E)$</span> with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut.  To prove the theorem we prove two lemmas:</p>
<p><strong>Lemma 1.</strong> <em>Weighted PDC reduces in polynomial time to (unweighted) PDC.</em></p>
<p><strong>Lemma 2.</strong> <em>MAX-CUT reduces in polynomial time to Weighted PDC.</em></p>
<p><em>Proof of Lemma 1.</em> Given an <span class="math-container">$n$</span>-vertex instance <span class="math-container">$G=(V,E)$</span> of weighted PDC with weights in <span class="math-container">$[-M, M]$</span>, where <span class="math-container">$M$</span> is polynomial in <span class="math-container">$|G|$</span>, the reduction outputs the graph <span class="math-container">$G'$</span> obtained from <span class="math-container">$G$</span> as follows.  Replace each vertex <span class="math-container">$v$</span> in <span class="math-container">$G$</span> by a clique <span class="math-container">$C_v$</span> of <span class="math-container">$|E|+1$</span> vertices, with all edges white.  For each edge <span class="math-container">$(u, v)$</span> of weight <span class="math-container">$w$</span> in <span class="math-container">$G$</span>, add <span class="math-container">$|w|$</span> edges between <span class="math-container">$C_u$</span> and <span class="math-container">$C_v$</span>, making them white if <span class="math-container">$w&lt;0$</span> and red if <span class="math-container">$w&gt;0$</span>.  Given any positive-weight cut <span class="math-container">$(A, B)$</span> in <span class="math-container">$G$</span>, the corresponding cut in <span class="math-container">$G'$</span> is <span class="math-container">$(A', B')$</span> where <span class="math-container">$A'= \bigcup_{v\in A} C_v$</span> and <span class="math-container">$B'=\bigcup_{v\in B} C_v$</span>.  The number of red edges minus white edges crossing <span class="math-container">$(A', B')$</span> is the weight of the cut <span class="math-container">$(A, B)$</span>.  So, if <span class="math-container">$G$</span> has a positive-weight cut, then <span class="math-container">$G'$</span> has a cut with more red than white edges.  Conversely, suppose <span class="math-container">$G'$</span> has a cut with more red than white edges.  The total number of red edges in <span class="math-container">$G'$</span> is at most <span class="math-container">$|E|M$</span>, so each clique <span class="math-container">$C_v$</span> must be entirely contained in one side of the cut or the other.  So the cut corresponds to a cut in <span class="math-container">$G$</span> that has positive weight.  This proves Lemma 1. <span class="math-container">$~~\Box$</span></p>
<p><em>Proof of Lemma 2.</em>  Given a MAX-CUT instance <span class="math-container">$(G=(V,E), k)$</span>, the reduction outputs the instance <span class="math-container">$G'$</span> of Weighted PDC defined as follows.  Obtain <span class="math-container">$G'$</span> from <span class="math-container">$G$</span> by giving every edge in <span class="math-container">$G$</span> weight 1, then adding two vertex <span class="math-container">$a$</span> and <span class="math-container">$b$</span>, each with edges to all other vertices.  Give each edge from <span class="math-container">$a$</span> or <span class="math-container">$b$</span> to a vertex in <span class="math-container">$G$</span> weight <span class="math-container">$-M$</span> where <span class="math-container">$M=|E|+1$</span>.  Give the edge <span class="math-container">$(a, b)$</span> weight <span class="math-container">$M|V|-k+1$</span>.  This completes the reduction.</p>
<p>Suppose there is a cut <span class="math-container">$(A, B)$</span> in <span class="math-container">$G$</span> with at least <span class="math-container">$k$</span> edges.  Then the cut <span class="math-container">$(A', B')$</span> in <span class="math-container">$G'$</span> where <span class="math-container">$A'=A \cup \{a\}$</span> and <span class="math-container">$B'=B\cup\{b\}$</span> has weight at least <span class="math-container">$k-|V|M + M|V|-k+1 = 1$</span>.  Conversely, suppose there is a positive-weight cut <span class="math-container">$(A', B')$</span> in <span class="math-container">$G'$</span>.  Vertices <span class="math-container">$a$</span> and <span class="math-container">$b$</span> cannot be on the same side of the cut, because if they are, the edge <span class="math-container">$(a, b)$</span> is not cut, while at least one edge out of <span class="math-container">$a$</span> or <span class="math-container">$b$</span> is cut, contributing <span class="math-container">$-M=-|E|-1$</span> to the cut weight, and each of the remaining edges (in <span class="math-container">$E$</span>) contributes at most 1.  So <span class="math-container">$a$</span> and <span class="math-container">$b$</span> are on different sides of the cut <span class="math-container">$(A', B')$</span>.  WLOG assume <span class="math-container">$a\in A'$</span> and <span class="math-container">$b\in B'$</span>.  Then (accounting for the edges out of <span class="math-container">$a$</span> and <span class="math-container">$b$</span>) the cut <span class="math-container">$(A, B)$</span> in <span class="math-container">$G$</span> where <span class="math-container">$A=A'\setminus \{a\}$</span> and <span class="math-container">$B=B'\setminus \{b\}$</span> must have at least <span class="math-container">$k$</span> edges.  So the reduction is correct. <span class="math-container">$~~\Box$</span></p>
<p>This reduction is similar to one by Peter Shor in <a href="https://cstheory.stackexchange.com/a/2318/8237">this answer</a> to a question about approximating MAX-CUT with negative edge weights.</p>

CC BY-SA 4.0
2020-09-09T17:23:56.503Z
Regarding your question above, I doubt that the problem is in P if you restrict to, say,  regular graphs with $O(1)$ degree.  No doubt MAX-CUT remains hard for such graphs, and I'd guess you can suitably modify the reduction above so that if the given MAX-CUT instance is regular with $O(1)$ degree, the reduction gives an instance of PDC that is sparse and regular.
Neal Young
CC BY-SA 4.0
2020-09-09T17:43:59.503Z
Great answer. Thanks!
dohmatob
CC BY-SA 4.0
2020-09-10T12:55:42.037Z
BTW, one easy case: if the graph has more red edges than white edges, there will be a vertex with more red edges than white edges incident to it, so that vertex alone will form a suitable cut.
Neal Young
CC BY-SA 4.0
2020-09-09T17:20:15.590Z
2020-09-09T17:25:49.057Z
2020-09-09T17:25:49.057Z
Neal Young
<p>Let <span class="math-container">$G=(V,E)$</span> be graph. Recall that a  cut of <span class="math-container">$G$</span> is (or can uniquely be identified with) a pair <span class="math-container">$(A,B)$</span> of nonempty subsets of <span class="math-container">$V$</span> which partition it. Given a cut <span class="math-container">$(A,B)$</span>, let <span class="math-container">$E(A,B) := \{(a,b) \in E \mid a \in A, b \in B\} = E \cap (A \times B)$</span>. Finally, let <span class="math-container">$E = E_1 \cup E_2$</span> be a given partitioning of the edges.</p>
<blockquote>
<p><strong>Question.</strong> What is an efficient way to generate a cut <span class="math-container">$(A,B)$</span> of <span class="math-container">$G$</span> such that <span class="math-container">$|E_1(A,B)| &gt; |E_2(A,B)|$</span> ?</p>
</blockquote>
<p><strong>Note.</strong> I'm fine with randomized algorithms. Also, in case one has the choice, I'd prefer a cut with minimal <span class="math-container">$|E(A,B)|$</span>.</p>

CC BY-SA 4.0
2020-09-09T11:31:13.933Z
This problem may be NP-hard.  Suggest you edit your question to clarify how fast an algorithm you are looking for, and whether you would accept a proof of NP-hardness as an answer.
Neal Young
CC BY-SA 4.0
2020-09-09T14:02:32.390Z
Ah, i felt it would be NP-hard, but didn't push it any further. Yes, I'd be fine with a transparent proof of NP-hardness.
dohmatob
CC BY-SA 4.0
2020-09-09T14:06:23.247Z
BTW, would if one adds structural constraints like: $G$ is sparse or (in an appropriate sense) or with sufficiently uniform per-node degree, etc. Can anything be salvaged from the situation ? Thanks in advance!
dohmatob
<ds.algorithms><graph-theory><graph-algorithms><linear-programming><enumeration>
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
dohmatob
# Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

(Asked by: username_0 on 2020-09-09)

Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in E \mid a \in A, b \in B\} = E \cap (A \times B)$. Finally, let $E = E\_1 \cup E\_2$ be a given partitioning of the edges.

> **Question.** What is an efficient way to generate a cut $(A,B)$ of $G$ such that $|E\_1(A,B)| > |E\_2(A,B)|$ ?

**Note.** I'm fine with randomized algorithms. Also, in case one has the choice, I'd prefer a cut with minimal $|E(A,B)|$.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, linear-programming, enumeration

> **Comments:**
> **username_1**: This problem may be NP-hard.  Suggest you edit your question to clarify how fast an algorithm you are looking for, and whether you would accept a proof of NP-hardness as an answer.  
> **username_0**: Ah, i felt it would be NP-hard, but didn't push it any further. Yes, I'd be fine with a transparent proof of NP-hardness.  
> **username_0**: BTW, would if one adds structural constraints like: $G$ is sparse or (in an appropriate sense) or with sufficiently uniform per-node degree, etc. Can anything be salvaged from the situation ? Thanks in advance!  

---

## 1 answers

### Answer by username_1 on 2020-09-09. Score: 6 | Accepted answer

**Theorem 1.** *The given problem is NP-hard, by reduction from MAX-CUT.*

*Proof.* Call the given problem Positive Discrepancy Cut (PDC). Define *weighted PDC* to be the generalization where the input is a graph $G=(V,E)$ with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut. To prove the theorem we prove two lemmas:

**Lemma 1.** *Weighted PDC reduces in polynomial time to (unweighted) PDC.*

**Lemma 2.** *MAX-CUT reduces in polynomial time to Weighted PDC.*

*Proof of Lemma 1.* Given an $n$-vertex instance $G=(V,E)$ of weighted PDC with weights in $[-M, M]$, where $M$ is polynomial in $|G|$, the reduction outputs the graph $G'$ obtained from $G$ as follows. Replace each vertex $v$ in $G$ by a clique $C\_v$ of $|E|+1$ vertices, with all edges white. For each edge $(u, v)$ of weight $w$ in $G$, add $|w|$ edges between $C\_u$ and $C\_v$, making them white if $w<0$ and red if $w>0$. Given any positive-weight cut $(A, B)$ in $G$, the corresponding cut in $G'$ is $(A', B')$ where $A'= \bigcup\_{v\in A} C\_v$ and $B'=\bigcup\_{v\in B} C\_v$. The number of red edges minus white edges crossing $(A', B')$ is the weight of the cut $(A, B)$. So, if $G$ has a positive-weight cut, then $G'$ has a cut with more red than white edges. Conversely, suppose $G'$ has a cut with more red than white edges. The total number of red edges in $G'$ is at most $|E|M$, so each clique $C\_v$ must be entirely contained in one side of the cut or the other. So the cut corresponds to a cut in $G$ that has positive weight. This proves Lemma 1. $~~\Box$

*Proof of Lemma 2.* Given a MAX-CUT instance $(G=(V,E), k)$, the reduction outputs the instance $G'$ of Weighted PDC defined as follows. Obtain $G'$ from $G$ by giving every edge in $G$ weight 1, then adding two vertex $a$ and $b$, each with edges to all other vertices. Give each edge from $a$ or $b$ to a vertex in $G$ weight $-M$ where $M=|E|+1$. Give the edge $(a, b)$ weight $M|V|-k+1$. This completes the reduction.

Suppose there is a cut $(A, B)$ in $G$ with at least $k$ edges. Then the cut $(A', B')$ in $G'$ where $A'=A \cup \{a\}$ and $B'=B\cup\{b\}$ has weight at least $k-|V|M + M|V|-k+1 = 1$. Conversely, suppose there is a positive-weight cut $(A', B')$ in $G'$. Vertices $a$ and $b$ cannot be on the same side of the cut, because if they are, the edge $(a, b)$ is not cut, while at least one edge out of $a$ or $b$ is cut, contributing $-M=-|E|-1$ to the cut weight, and each of the remaining edges (in $E$) contributes at most 1. So $a$ and $b$ are on different sides of the cut $(A', B')$. WLOG assume $a\in A'$ and $b\in B'$. Then (accounting for the edges out of $a$ and $b$) the cut $(A, B)$ in $G$ where $A=A'\setminus \{a\}$ and $B=B'\setminus \{b\}$ must have at least $k$ edges. So the reduction is correct. $~~\Box$

This reduction is similar to one by Peter Shor in [this answer](https://cstheory.stackexchange.com/a/2318/8237) to a question about approximating MAX-CUT with negative edge weights.

> **Comments:**
> **username_1**: Regarding your question above, I doubt that the problem is in P if you restrict to, say,  regular graphs with $O(1)$ degree.  No doubt MAX-CUT remains hard for such graphs, and I'd guess you can suitably modify the reduction above so that if the given MAX-CUT instance is regular with $O(1)$ degree, the reduction gives an instance of PDC that is sparse and regular.  
> **username_0**: Great answer. Thanks!  
> **username_1**: BTW, one easy case: if the graph has more red edges than white edges, there will be a vertex with more red edges than white edges incident to it, so that vertex alone will form a suitable cut.  

---

