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}|\ge k$ is called a $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^{\prime }=X\cap Y$ and $T^{\prime }=\bar{X}\cap Y$. We can try to find the min-cut of all possible $S$ and $T$ such that $S^{\prime }\subset S$,$T^{\prime }\subset T$ and $|S|=|T|=k$. Since we don’t know what $S^{\prime }$ and $T^{\prime }$ are, we will try all $2^k$ possibilities. Here the $S^{\prime }$ and $T^{\prime }$ 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 $\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)+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:

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.

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^{\prime }$ 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^{\prime }$ 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^{\prime }$.

Otherwise, $e$ is an edge crossing every min-$2$-restricted cut. Let $e=uv$ and and wlog $\mathrm{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 $\mathrm{deg}(u)\mathrm{deg}(v)\le \delta n=O(m)$ flow computations.

References