JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Maximum Flow tutorial Re: Finding Minimum Edges Minimum Cut Revision History (3 edits)
Re: Finding Minimum Edges Minimum Cut (response to post by mogers)
(some explanations related to the first post are in edit)

Did you even read my post ? :)

Yes.

It doesn't work if we want the minimum set of edges with smallest index.

Well, do we need it? :) I mean, is there any more or less practical problem that asks it?
Here is a tough case: Source and Sink are both connected to a complete graph K_n, all egdes have the same capacity.
Consider any decomposition of the vertices of K_n into sets of != 2 vertices. Take any set S with |S| >= 3 and form a cycle with its vertices. In the 'obvious' minimum cut there are only edges (Source, v) and (v, Sink) but it is clear that with such cycle formed you can take any(but only one at a time) vertice v from it and change the edge (Source, v) to (v, next[v]). This minimum cut will contain the same number of edges and you can play this trick with any vertice in any set of any decomposition. The number of such 'min cuts' can be calculated, but even now we can say it's large enough.
Re: Finding Minimum Edges Minimum Cut (response to post by mogers)
Did you even read my post ? :)

Yes. It is vague enough to be misunderstood.

        edge 2     edge 1
Source -------> A -------> Sink

This cannot be a correct example of a residual network because Sink can be reached from Source.
Consider three possible options:
1. capacity(edge 1) > capacity(edge 2) = X
Here we can push X units of flow from Source to Sink which leads to
        edge 2     edge 1
Source <------- A <-------> Sink

2. capacity(edge 1) < capacity(edge 2), which in the same way leads to
        edge 2     edge 1
Source <-------> A <------- Sink

In both cases dfs yields the correct answer

3. capacity(edge 1) = capacity(edge 2)
Here only two but not three edges(unlike above) are left in the residual network:
        edge 2     edge 1
Source <------- A <------- Sink


Here what we need is a matter of definitions. In fact, dfs works right if
you want any minimum cut.

It doesn't work if we want the minimum set of edges with smallest index.

Oh, now I get what you wanted to say.
Well, do we need it? :) I mean, is there any more or less practical problem that asks it?
After thinking more about it, I have no idea of how to do it :)
Here is a tough case: Source and Sink are both connected to a complete graph K_n(which has only edges of capacity n) with egdes of capacity 1. Depending on how you push the flow, you can form a lot(if not all) of subsets of edges which will form a cut.

edit: some new thoughts
Re: Finding Minimum Edges Minimum Cut (response to post by mogers)
Did you even read my post ? :)

Yes. It is vague enough to be misunderstood.

        edge 2     edge 1
Source -------> A -------> Sink

This cannot be a correct example of a residual network because Sink can be reached from Source.
Consider three possible options:
1. capacity(edge 1) > capacity(edge 2) = X
Here we can push X units of flow from Source to Sink which leads to
        edge 2     edge 1
Source <------- A <-------> Sink

2. capacity(edge 1) < capacity(edge 2), which in the same way leads to
        edge 2     edge 1
Source <-------> A <------- Sink

In both cases dfs yields the correct answer

3. capacity(edge 1) = capacity(edge 2)
Here only two but not three edges(unlike above) are left in the residual network:
        edge 2     edge 1
Source <------- A <------- Sink


Here what we need is a matter of definitions. In fact, dfs works right if
you want any minimum cut.

It doesn't work if we want the minimum set of edges with smallest index.

Oh, now I get what you wanted to say.
Well, do we need it? :) I mean, is there any more or less practical problem that asks it? Even if there is(which would be strange) I think that a slightly improved dfs still would do. The example above can be solved by looking one vertice forward. Maybe it works in general case, I'm not quite sure.


edit: nothing special
Re: Finding Minimum Edges Minimum Cut (response to post by mogers)
Did you even read my post ? :)

Yes.

        edge 2     edge 1
Source -------> A -------> Sink

This cannot be a correct example of a residual network because Sink can be reached from Source.
Consider three possible options:
1. capacity(edge 1) > capacity(edge 2) = X
Here we can push X units of flow from Source to Sink which leads to
        edge 2     edge 1
Source <------- A <-------> Sink

2. capacity(edge 1) < capacity(edge 2), which in the same way leads to
        edge 2     edge 1
Source <-------> A <------- Sink

3. capacity(edge 1) = capacity(edge 2)
Here only two but not three edges(unlike above) are left in the residual network:
        edge 2     edge 1
Source <------- A <------- Sink


In all these cases dfs yields the correct answer.