CODEWITHSUNDEEP
algorithmgraphunique
Daniel Buckmaster
Daniel Buckmaster

Reputation: 7186

Determining the uniqueness of a min-cut

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?

Upvotes: 13

Views: 25850

Answers (4)

arad
arad

Reputation: 33

Based on Eran Zimmerman Gonen answer:
what about this flow graph:
G=(V,E), s.t V={s,a,b,c,t}, E={(s,a),(a,b),(b,c),(c,t)}.
the capacity of all edges is 1, so as the flow.
s-(1/1)->a-(1/1)->b-(1/1)->c-(1/1)->t
So, based on the residual graph, I have a min-cut S={s}.
Starting from t I am getting S'={t,c,d,a}.
Looking at 7th label, V/S' = {s} = S which means I have only one min-cut, but I have many more: S={s}, S'={s,a}, S''={s,a,b}, S''' = {s,a,b,c}

Upvotes: 0

Jayant Apte
Jayant Apte

Reputation: 41

Given that max flow/min cut problem is really a Linear programming problem(primal/dual respectively), I reckon any method to check uniqueness of LP solution and finding alternative optimum solution if its not unique can be used in this context. I googled to find this paper :On the Uniqueness of Solutions to Linear Programs EDIT 1: Based on suggestion by dzhuang, for those who are unaware that maxflow-mincut theorem is a special case of strong duality theorem in linear programming, here is the link explaining this nuance: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Linear_program_formulation

Upvotes: 3

Eran Zimmerman Gonen
Eran Zimmerman Gonen

Reputation: 4507

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.

Upvotes: 20

davin
davin

Reputation: 45555

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.

Upvotes: 28

Related Questions