JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Finding Minimum Edges Minimum Cut | Reply
First of all, really nice article, _efer_ !

You explained well how to find a minimum edges minimum cut, but we actually find only the value of the minimum cut and the number of edges it has. How do we actually find which edges exactly would make such a cut from the residual network?
Re: Finding Minimum Edges Minimum Cut (response to post by zdravko_b) | Reply
Let S be the set of all vertices reachable from the source(including the source itself) and T = V \ S. Then the pair (S, T) forms a minimum cut and, therefore, dfs is all you need.
Re: Finding Minimum Edges Minimum Cut (response to post by fetetriste) | Reply
Dfs from the source returns the minimum cut closest to the source. It doesn't work if we want the minimum set of edges with smallest index.

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


Using that method we would get edge 2, but the answer is edge 1.

Anyone know how to solve this ?
Re: Finding Minimum Edges Minimum Cut (response to post by mogers) | Reply
Dfs should be applied to the residual network. You get a 2-colouring of the vertices, black are reachable from the source and white are not.
Edges from black to white vertices(and only them) are what you need.
Re: Finding Minimum Edges Minimum Cut (response to post by fetetriste) | Reply
Did you even read my post ? :)

I said that that method answers edge number 2 because in the residual network there isn't flow from the source to A. So the 2 sets are "Source" and "A,Sink".
Re: Finding Minimum Edges Minimum Cut (response to post by mogers) | Reply
(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 fetetriste) | Reply
I apologize, it could be clearer but i think that if you had faced a problem about this, i think that you would understand what i asked.

I didn't say that it was the residual graph. It is the original one. I think that there is only one thing that is vague: i didn't mention edge capacities. This was kind of intentional to not complicate the draw. For me the lack of this info, would point that capacities were equal (that was my intention).

        edge 2     edge 1
Source <------- A <------- Sink


In this case both "edge 2" and "edge 1" are possible answers, but "edge 1" has minimum index.

"Well, do we need it? :) I mean, is there any more or less practical problem that asks it?"

A problem from usaco training discussed here. I didn't understand well why the trick works. And the reference solution (used that method: dfs from the source) was changed because it is wrong.
Re: Finding Minimum Edges Minimum Cut (response to post by mogers) | Reply
Oh, I finally got what you meant and rewrote the post bit( before you posted :P )
RSS