The Art Gallery Guardian

Minimum cuts with restrictions


There is a nice algorithm design technique for cuts: fix a small number of partial solutions, and guess all possible solutions built from the partial solution. Here are two demonstrations.

1 \(k\)-size-cut

A cut \((X,\bar{X})\) such that both \(|X|,|\bar{X}|\geq k\) is called a \(k\)-size-cut.

Problem1

Given a graph \(G\), find a minimum \(k\)-size-cut.

The standard algorithm is based on finding all possible min-\(ST\)-cut, where \(S,T\) are all possible disjoint sets of size \(k\). The running time is \(O(n^{2k})\) min-cut computations.

One can improve it by first fix an arbitrary set of \(k\) vertices \(Y\). Consider a min-\(k\)-size-cut \((X,\bar{X})\). Let \(S'=X\cap Y\) and \(T'=\bar{X}\cap Y\). We can try to find the min-cut of all possible \(S\) and \(T\) such that \(S'\subset S\),\(T'\subset T\) and \(|S|=|T|=k\). Since we don't know what \(S'\) and \(T'\) are, we will try all \(2^k\) possibilities. Here the \(S'\) and \(T'\) are the partial solutions. This gives us an algorithm with running time \(O(2^k n^k)\) min-cut computations. The idea is also used in computing matroid connectivity.

A further improvement depending on the fact that there are only \(O(n^{k-1})\) cuts we try to avoid. We can enumerate all the cuts from smallest to largest, with a delay of a single application of Hao-Orlin algorithm [1]. The running time of Hao-Orlin algorithm is approximately a single maximum flow. One of the smallest \({n \choose k-1}+1\) cuts is the min-\(k\)-size-cut. The running time is \(O(n^{k-1})\) Hao-Orlin computation [2].

It's interesting to wonder if the running time can be improved, especially for the case where \(k=2\). Fix a set \(S=\{s,t\}\) of size \(2\). There are two cases, either the min-\(2\)-size-cut crosses \(S\), then one of the the \(3\) smallest \(st\)-cuts is our solution. The other case is \(S\) is on one side of the min-\(2\)-size-cut, and we are interested in finding a cut so the side doesn't contain \(S\) has at least \(2\) vertices.

This prompt a interesting problem:

Problem2

Find the second smallest \(st\)-cut, if we already have a min-\(st\)-cut and it's corresponding flow(or some other useful information obtained through a push relabel flow computation).

Can we solve this in \(O(m)\) time? What if we also know the min-\(st\)-cut is induced by \(t\)?

2 \(2\)-restricted-cut

A problem which appeared as a question on cstheory.

Problem3

Given a graph \(G\), find the minimum cut under the constraint that each side is connected and has at least \(2\) vertices. (Assume it exists).

This is the \(k\)-restricted edge connectivity problem when \(k=2\).

\(\lambda_k(G)\), the \(k\)-restricted edge connectivity of \(G\), defined as the smallest number of edges such that the removal result exactly \(2\) connected component, each with at least \(k\) vertices. The rest of the article describes the algorithm by Esfahanian and Hakimi [3].

\(\lambda_2(G)\) can be found in \(O(m^2)\) flow computations. The idea is to contract any two independent edges \(e\) and \(e'\) to \(s\) and \(t\), and then find a \(st\)-min-cut. The cut will give us the desired partition.

It can be improved with the idea of fixing a partial solution. Consider a single edge \(e\) that incident to a vertex with lowest degree, contract it to vertex \(s\). Pick another edge \(e'\) that not incident to \(s\), we contract it to \(t\). The min-cut between \(s\) and \(t\) reflects a \(2\)-restricted cut. If \(e\) is on one side of the min-\(2\)-restricted cut, then this algorithm finds it in \(O(m)\) flow computations by trying all possible \(e'\).

Otherwise, \(e\) is an edge crossing every min-\(2\)-restricted cut. Let \(e=uv\) and and wlog \(\deg(u)=\delta\), the min degree. We fix another partial solutions where \(u\) and \(v\) are on different side of the min-\(2\)-restricted cut. One can contract any edge incident to \(u\) and any edge incident to \(v\) and apply a flow computation. There are at most \(\deg(u) \deg(v)\leq \delta n = O(m)\) flow computations.

References

[1] J. Hao, J. Orlin, A faster algorithm for finding the minimum cut in a directed graph, Journal of Algorithms. 17 (1994) 424–446 10.1006/jagm.1994.1043.

[2] L.-P. Yeh, B.-F. Wang, H.-H. Su, Efficient algorithms for the problems of enumerating cuts by non-decreasing weights, Algorithmica. 56 (2009) 297–312 10.1007/s00453-009-9284-5.

[3] A.-H. Esfahanian, S. Hakimi, On computing a conditional edge-connectivity of a graph, Information Processing Letters. 27 (1988) 195–199 10.1016/0020-0190(88)90025-7.

Posted by Chao Xu on 2016-04-24.
Tags: cut.