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 kk-size-cut

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

Problem1

Given a graph GG, find a minimum kk-size-cut.

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

One can improve it by first fix an arbitrary set of kk vertices YY. Consider a min-kk-size-cut (X,Xˉ)(X,\bar{X}). Let S=XYS'=X\cap Y and T=XˉYT'=\bar{X}\cap Y. We can try to find the min-cut of all possible SS and TT such that SSS'\subset S,TTT'\subset T and S=T=k|S|=|T|=k. Since we don't know what SS' and TT' are, we will try all 2k2^k possibilities. Here the SS' and TT' are the partial solutions. This gives us an algorithm with running time O(2knk)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(nk1)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 (nk1)+1{n \choose k-1}+1 cuts is the min-kk-size-cut. The running time is O(nk1)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=2k=2. Fix a set S={s,t}S=\{s,t\} of size 22. There are two cases, either the min-22-size-cut crosses SS, then one of the the 33 smallest stst-cuts is our solution. The other case is SS is on one side of the min-22-size-cut, and we are interested in finding a cut so the side doesn't contain SS has at least 22 vertices.

This prompt a interesting problem:

Problem2

Find the second smallest stst-cut, if we already have a min-stst-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)O(m) time? What if we also know the min-stst-cut is induced by tt?

2 22-restricted-cut

A problem which appeared as a question on cstheory.

Problem3

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

This is the kk-restricted edge connectivity problem when k=2k=2.

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

λ2(G)\lambda_2(G) can be found in O(m2)O(m^2) flow computations. The idea is to contract any two independent edges ee and ee' to ss and tt, and then find a stst-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 ee that incident to a vertex with lowest degree, contract it to vertex ss. Pick another edge ee' that not incident to ss, we contract it to tt. The min-cut between ss and tt reflects a 22-restricted cut. If ee is on one side of the min-22-restricted cut, then this algorithm finds it in O(m)O(m) flow computations by trying all possible ee'.

Otherwise, ee is an edge crossing every min-22-restricted cut. Let e=uve=uv and and wlog deg(u)=δ\deg(u)=\delta, the min degree. We fix another partial solutions where uu and vv are on different side of the min-22-restricted cut. One can contract any edge incident to uu and any edge incident to vv and apply a flow computation. There are at most deg(u)deg(v)δn=O(m)\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 .
Tags: cut.