Determining the uniqueness of a min-cut

Question

Disclaimer: this was a homework problem. The deadline has passed now, so discussions can continue without needing to worry about that.

The problem I'm struggling with is to determine whether a particular minimum s-t cut in a graph G = (V, E) is unique. It's simple enough to find some min-cut using a max-flow algorithm as per this example, but how would you show it's the min-cut?

Answer 1

Ok, since you don't want the whole answer right away, I'm gonna give you a few hints. Read as many as you feel are necessary for you, and if you give up - go ahead and read them all.

1:
The cut is unique iff there is no other min-cut.

2:
If you succeed in finding a different min-cut, then the first min-cut isn't unique.

3:
Your link gave us one min-cut, which is all the reachable vertices from s in the residual graph. Can you think of a way to obtain a different cut, not necessarily the same?

4:
Why did we take those vertices reachable from s in particular?

5:
Maybe we can do something analogous from t?

6:
Look at the same residual graph, starting at t. Look at the group of vertices reachable from t in the reverse direction of the arrows (meaning all the vertices which can reach t).

7:
This group is also a min-cut (or actually S \ that group, to be precise).

8 (final answer):
If that cut is identical to your original cut, then there is only one. Otherwise, you just found 2 cuts, so the original one can't possibly be unique.

Answer 2

Outline:

Given a minimum S-T cut, (U,V) with cut-edges E', we make one simple observation: If this minimum cut is not unique, then there exists some other minimum cut with a set of cut-edges E'', such that E'' != E'.

If so, we can iterate over each edge in E', add to its capacity, recalculate the max flow, and check if it increased.

As a result of the observation above, there exists an edge in E' that when increased, the max flow doesn't increase iff the original cut is not unique.

I'll leave you to fill in the details and prove that this is a poly-time task.