# Decide whether a flow graph has a single min-cut

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.

• Please edit your question to specify whether this is an undirected graph, or whether it is a directed graph, and whether we are provided a source $s$ and sink $t$ or are willing to accept any cut. Also, can you explain the motivation behind this question, or the source where you encountered this? If it was in a textbook, what was the textbook describing, or what were you mostly studying in your course?
– D.W.
Jan 23 at 18:06
• The question was edited. The graph is a directed graph, The motivation behind this question is the thoughts I've encounterd when studying flow networks and maximum flow (including min cuts and max vertex cover). Im not sure on how given a provided sink and source going to assist in this, but we can assume we are not provided $s,t$ and we can add them ourselves to create a flow networks. We're currently on flow subjects, with BFS/DFS/ Ford-Fulkerson/Edmonds Karp algorithms already taught. Jan 24 at 9:23

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

• This was exactly the algorithm I was in need of. excellent explanation, thank you very much! Jan 24 at 15:31
• You are welcome! Jan 24 at 15:32

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.

• This observation is understandable, and I am aware of it. However, I am unsure on the ways/algorithm to check whether a minimum cut is unique (which means it is the only minimum cut in the graph, under the given maximum flow) or there are other minimum cuts, and as a result, a different flow function with the same maximum flow (I'm not sure if I mixed some things here, single min cut=single max flow function?) Jan 24 at 9:26
• You can check if the given minimum cut is unique by trying to set each edge (individually) to capacity $\infty$. Then, if every time the cut increases, it is unique, otherwise you have another minimum cut with the same cost. Jan 24 at 14:38

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') - 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.

• I think this solves a different problem, John. L provided a linear time solution to the problem. Jan 24 at 15:32