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)|$ 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)| &gt; |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)|$.
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&lt;0$ and red if $w&gt;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 to a question about approximating MAX-CUT with negative edge weights.