# 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,Xˉ)$ such that both $∣X∣,∣Xˉ∣≥k$ is called a $k$-size-cut.

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,Xˉ)$. Let $S_{′}=X∩Y$ and $T_{′}=Xˉ∩Y$. We can try to find the min-cut of all possible $S$ and $T$ such that $S_{′}⊂S$,$T_{′}⊂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 $(k−1n )+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:

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.

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

$λ_{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].

$λ_{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 $g(u)=δ$, 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 $g(u)g(v)≤δn=O(m)$ flow computations.

# References

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

**Efficient algorithms for the problems of enumerating cuts by non-decreasing weights**, Algorithmica. 56 (2009) 297–312 10.1007/s00453-009-9284-5.

**On computing a conditional edge-connectivity of a graph**, Information Processing Letters. 27 (1988) 195–199 10.1016/0020-0190(88)90025-7.