# Global min-cut with parity constraint on the edges

In a discussion with Patrick Lin, a nice problem was born.

Let $δ(S)$ to be the set of edges with exactly one endpoint in $S$. $δ_{−}(S)$ to be the set of edges with its head in $S$ and tail in $V∖S$. Given a non-negative weighted graph, we define the cut function $f:2_{V}→R_{+}$ to be $f(S)=∑_{e∈δ(S)}w(e)$. For directed graphs, $f(S)=∑_{e∈δ_{−}(S)}w(e)$. $f(S)$ is called the value of the cut $S$.

Let $k$ be a constant, we consider the following problem.

Give a graph and $k$ set of edges $F_{1},…,F_{k}$, $a_{1},…,a_{k},b$. Find a cut $S$ satisfies that $∣δ(S)∩F_{i}∣≡a_{i}(modb)$ for all $i$, and the value is minimized.

We will try to reduce this problem to the following

Given $T_{1},…,T_{k}$ and a submodular function $f$. Find a set $S$ such that $∣T_{i}∩S∣≡a_{i}(modb)_{i}$, and $f(S)$ is minimized.

The above problem is known as submodular minimization under congruence constraints. It is known to be solvable in polynomial time under certain conditions on the $b_{i}$’s [1]. In particular, when all $b_{i}$ are constants.

Patrick showed a the following construction. Create a new graph $G_{′}$ as follows. For each $uv$ in $E$,
split it into edges $ux$, $xy$, $yv$,
$w(ux)=w(yv)=∞$, and $w(xy)=w(uv)$. Let $T_{i}$ contains the vertex $x$ and $y$ if
$uv∈F_{i}$.

We now solve the submodular minimization under congruence constraints
problem on input $f$, which is the cut
function for $G_{′}$, and same $a_{1},…,a_{k}$ and $b_{1},…,b_{k}=2$.