Thursday, December 8, 2011

How to verify the unique min-cut

How to verify that there is only one min-cut in a graph G(V, E), which have one sink, t, and a source, s. The first idea is as followed:
  • run the max-flow algorithm, such as Ford-Fulkerson or Edmonds-Karp, and keep the residual graph as G`.
  • run DFS, from s and t, on G` and find out a reachable set R1 and R2.
  • if and only if R1 + R2 = E, then return true, otherwise, return false.
This method uses a constraint of min-cut that all the edges through a min-cut in a max-flow graph have 0 capacity. So, if there are two min-cut, there must be another “bottleneck” that does not allow DFS to reach the node.
For a directed graph G(V, E). We could do the following to verify the unique or not.
  • run the max-flow algorithm;
  • for each edge e though the min cut, increase the capacity;
  • if the max flow does not change, the min cut is not unique; otherwise, it is unique.

4 comments:

  1. if the max flow does not change, the min cut is unique; otherwise, it is not.

    这句话是不是说反了?

    ReplyDelete
    Replies
    1. You are right! I have fixed that error.

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. If you run DFS from t in the residual graph then you'll reach s so R2=V (I think you should have written R1+R2=V).

    ReplyDelete