# 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)| > |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)|$$.

• 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. Sep 9 '20 at 11:31
• 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. Sep 9 '20 at 14:02
• 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! Sep 9 '20 at 14:06

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 to a question about approximating MAX-CUT with negative edge weights.

• 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. Sep 9 '20 at 17:23
• Great answer. Thanks! Sep 9 '20 at 17:43
• 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. Sep 10 '20 at 12:55