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

A cut such that both is called a -size-cut.

Problem1

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

The standard algorithm is based on finding all possible min--cut, where are all possible disjoint sets of size . The running time is min-cut computations.

One can improve it by first fix an arbitrary set of vertices . Consider a min--size-cut . Let and . We can try to find the min-cut of all possible and such that , and . Since we don’t know what and are, we will try all possibilities. Here the and are the partial solutions. This gives us an algorithm with running time min-cut computations. The idea is also used in computing matroid connectivity.

A further improvement depending on the fact that there are only 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 cuts is the min--size-cut. The running time is Hao-Orlin computation [2].

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

This prompt a interesting problem:

Problem2

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

Can we solve this in time? What if we also know the min--cut is induced by ?

2 -restricted-cut

A problem which appeared as a question on cstheory.

Problem3

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

This is the -restricted edge connectivity problem when .

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

can be found in flow computations. The idea is to contract any two independent edges and to and , and then find a -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 that incident to a vertex with lowest degree, contract it to vertex . Pick another edge that not incident to , we contract it to . The min-cut between and reflects a -restricted cut. If is on one side of the min--restricted cut, then this algorithm finds it in flow computations by trying all possible .

Otherwise, is an edge crossing every min--restricted cut. Let and and wlog , the min degree. We fix another partial solutions where and are on different side of the min--restricted cut. One can contract any edge incident to and any edge incident to and apply a flow computation. There are at most flow computations.

References

[1]
J.X. Hao, J.B. 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.L. 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.