5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Neal Young Sep 9 at 11:31
  • $\begingroup$ 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. $\endgroup$ – dohmatob Sep 9 at 14:02
  • $\begingroup$ 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! $\endgroup$ – dohmatob Sep 9 at 14:06
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Neal Young Sep 9 at 17:23
  • $\begingroup$ Great answer. Thanks! $\endgroup$ – dohmatob Sep 9 at 17:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Neal Young Sep 10 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.