The Art Gallery Guardian

Global min-cut with parity constraint on the edges

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

Let δ(S)\delta(S) to be the set of edges with exactly one endpoint in SS. δ(S)\delta^-(S) to be the set of edges with its head in SS and tail in VSV\setminus S. Given a non-negative weighted graph, we define the cut function f:2VR+f:2^V\to \R^+ to be f(S)=eδ(S)w(e)f(S) = \sum_{e\in \delta(S)} w(e). For directed graphs, f(S)=eδ(S)w(e)f(S) = \sum_{e\in \delta^-(S)} w(e). f(S)f(S) is called the value of the cut SS.

Let kk be a constant, we consider the following problem.


Give a graph and kk set of edges F1,,FkF_1,\ldots,F_k, a1,,ak,ba_1,\ldots,a_k,b. Find a cut SS satisfies that δ(S)Fiai(modb)|\delta(S)\cap F_i|\equiv a_i \pmod b for all ii, and the value is minimized.

We will try to reduce this problem to the following

Problem2submodular minimization under congruence constraints

Given T1,,TkT_1,\ldots,T_k and a submodular function ff. Find a set SS such that TiSai(modb)i|T_i\cap S| \equiv a_i\pmod b_i, and f(S)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 bib_i's [1]. We sketch the reductions.

1 Undirected case

In the undirected case, we only consider when b=2b=2. Patrick showed a the following construction. Create a new graph GG' as follows. For each uvuv in EE, split it into edges uxux, xyxy, yvyv, w(ux)=w(yv)=w(ux)=w(yv)=\infty, and w(xy)=w(uv)w(xy)=w(uv). Let TiT_i contains the vertex xx and yy if uvFiuv\in F_i.
We now solve the submodular minimization under congruence constraints problem on input ff, which is the cut function for GG', and same a1,,aka_1,\ldots,a_k and b1,,bk=2b_1,\ldots,b_k=2.

2 Directed case

In the directed case, a similar approach works. But now, instead of mod  2\mod 2, we can do mod  b\mod b for any bb. We consider the same approach.
(u,v)E(u,v) \in E split into (u,x1),,(xb,v)(u,x_1),\ldots,(x_b,v) and w(u,x1)=w(u,v)w(u,x_1)=w(u,v), w(xi,xi+1)=w(x_i,x_{i+1})=\infty, w(xb,v)=w(x_b,v)=\infty. Now, let TiT_i contain vertices x1,,xbx_1,\ldots,x_b of uvFiuv\in F_i.


[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 .
Tags: algorithms, min-cut.