 # 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 . 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 .

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 .

$\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

 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.

 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.

 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.