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} \to R^{+}$ to be $f (S) = \sum_{e \in δ (S)} w (e)$ . For directed graphs, $f (S) = \sum_{e \in δ^{-} (S)} w (e)$ . $f (S)$ is called the value of the cut $S$ .

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

Problem1

Give a graph and $k$ set of edges $F_{1}, \dots, F_{k}$ , $a_{1}, \dots, a_{k}, b$ . Find a cut $S$ satisfies that $∣ δ (S) \cap F_{i} ∣ \equiv a_{i} (mod b)$ for all $i$ , and the value is minimized.

We will try to reduce this problem to the following

Problem2submodular minimization under congruence constraints

Given $T_{1}, \dots, T_{k}$ and a submodular function $f$ . Find a set $S$ such that $∣ T_{i} \cap S ∣ \equiv a_{i} (mod b)_{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$ , $x y$ , $y v$ , $w (ux) = w (y v) = \infty$ , and $w (x y) = w (uv)$ . Let $T_{i}$ contains the vertex $x$ and $y$ if $uv \in 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}, \dots, a_{k}$ and $b_{1}, \dots, b_{k} = 2$ .

References

[1]

M. Nägele, B. Sudakov, R. Zenklusen, Submodular minimization under congruency constraints, in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial; Applied Mathematics, Philadelphia, PA, USA, 2018: pp. 849–866.

Posted by Chao Xu on 2018-11-06.

Tags: algorithms, min-cut.