Global min-cut with parity constraint on the edges
In a discussion with Patrick Lin, a nice problem was born.
Let to be the set of edges with exactly one endpoint in . to be the set of edges with its head in and tail in . Given a non-negative weighted graph, we define the cut function to be . For directed graphs, . is called the value of the cut .
Let be a constant, we consider the following problem.
Give a graph and set of edges , . Find a cut satisfies that for all , and the value is minimized.
We will try to reduce this problem to the following
Given and a submodular function . Find a set such that , and 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 ’s . We sketch the reductions.
1 Undirected case
In the undirected case, we only consider when . Patrick showed a the following construction. Create a new graph as follows. For each in , split it into edges , , , , and . Let contains the vertex and if .
We now solve the submodular minimization under congruence constraints problem on input , which is the cut function for , and same and .
2 Directed case
In the directed case, a similar approach works. But now, instead of , we can do for any . We consider the same approach.
split into and , , . Now, let contain vertices of .
 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.