Equivalence between MIN UNCUT and MIN-CSP_XOR

Question

In this paper

Agarwal, Amit, et al. "O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems." Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. 2005.

Agarwal et al. claim that the following two problems are equivalent.

Consider boolean variables $b_1,\dots ,b_n$ and a set of constraints of the form $b_i \oplus b_j = 0$ and $b_i \oplus b_j = 1$. The goal is to minimize the number of unsatisfied constraints.

and

Given a graph $G=(V,E)$ find a cut that minimizes the number of uncut edges.

If constraints were only of the form $b_i \oplus b_j = 1$, the equivalence is straightforward. However, if we also consider constraints of the form $b_i \oplus b_j = 0$, the first formulation seems more general to me.

How are these equivalent?

Answer 1

Suppose we are given a set of constraints of the form $b_i \oplus b_j = c$. We construct a graph with one vertex corresponding to each $b_i$. For each constraint of the form $b_i \oplus b_j = 1$, we add an edge $\{i,j\}$. For each constraint of the form $b_i \oplus b_j = 0$, we add a new vertex $x$, and two edges $\{i,x\},\{j,x\}$.

We can think of a cut as a partition of the vertices into two parts. For a constraint of the form $b_i \oplus b_j = 1$, the constraint is unsatisfied iff $i,j$ belong to the same part iff $\{i,j\}$ is uncut. For a constraint of the form $b_i \oplus b_j = 0$, there are two cases:

• If the constraint is unsatisfied, then $i,j$ belong to different parts, and so exactly one of the edges $\{i,x\},\{j,x\}$ is uncut.

• If the constraint is not unsatisfied, then $i,j$ belong to the same part, and so (depending on the location of $x$) either zero or two of the edges $\{i,x\},\{j,x\}$ are uncut. Since we are aiming to minimize the number of uncut edges, we can assume that zero are uncut.

In total, the number of unsatisfied constraints is the same as the number of uncut edges.