Decide whether a flow graph has a single min-cut

Question

The problem is whether a graph (which we represent as a flow network) has a single min-cut, or there could be multiple min cuts with the same maximum flow value, I've yet to encounter a well explained algorithm for solving this problem, let alone a complexity anaylsis or proof.

I was not able to find the exact resource of information to help me answer the problem. I'm not sure where else to search, therefore I thought asking here could perhaps help me better my understanding of the problem and the algorithms that help solving them.

Answer 1

Here is a simple algorithm that determines whether a flow network $G=(V, E, c)$ with source $s$ and sink $t$ has a single min-cut or not.

1. Find a maximum flow $f$ of $G$. Let $R_f$ be the residual network of $G$ with respect to $f$.
2. Let $X$ be the set of all nodes that are reachable from $s$ in $R_f$.
3. Let $Y$ be the set of all nodes from which $t$ is reachable or, what is equivalent, all nodes reachable from $t$ in $R_f$ with all direction of flow capacity reversed.
4. If $X\cup Y=V$, there is a unique minimum cut (which is $(X,Y)$). Otherwise, there are more than one minimum cut.

Why is the algorithm above correct?

First, we know that $(X, V\setminus X)$ is a minimum cut. By symmetry, so is $(V\setminus Y, Y)$.

Suppose $(S,T)$ is an arbitrary minimum-cut of $G$ where $s\in S$ and $t\in T$. This post tells that $X$ is contained in $S$. By symmetry, $Y$ is contained in $T$. Hence, $(S,T)$ is the unique minimum-cut iff $X\cup Y=V$.

Time-complexity of the algorithm

It mostly depends on the complexity of the algorithm that is used to compute a maximum flow.

It takes $O(E)$ time to compute $X$ and $Y$, given the max-flow $f$.

It takes $O(V)$ time to check whether $X=Y$.

Answer 2

If you're talking about a certain residual graph, the cut is unique, but in the flow network, there can be many (exponentially, even) minimum cuts.

Consider a simple path with $n$ vertices, each edge with capacity 1. There are $n-1$ minimum cuts, one for each edge. But in the residual graph, you will always get the unique cut being the first edge.

Answer 3

The idea is simply find a single min-cut $(S, T)$, then increase each one (seperately) of its crossing edges' capacity by a "tiny-tiny" $\epsilon>0$ then run min-cut algorithm again and check if there's any difference.

If there's another (let's a single one W.L.O.G) min-cut $(S', T')$, meaning (inter alia) there exists an edge $e\in (S, T)$ such that $e\notin (S', T')$, in the algorithm - when $e$'s capacity would change $c'(e)=c(e)+\epsilon$, the min-cut algorithm would detect $(S', T')\not=(S, T)$ and therefore we can conclude there existed another min-cut.

In general, notice that if $\epsilon$ was too high we could detect a different (rather than $(S, T)$) cut although it might not be a min-cut in case that $c(S', T')<c(S, T)+\epsilon$ - that's why we set $\epsilon$ as small as possible, I think it's pretty obvious but still wanted to mention that.

This algorithm's time complexity is $O(E\cdot M)$ where $O(M)$ is the min-cut detection algorithm's complexity.