CODEWITHSUNDEEP
algorithm
user1199556
user1199556

Reputation: 11

s-t min cuts intersection

I'm trying to find the proof for the following network flow problem:

therer is a graph G = (V, E).If you have two s-t min cuts, show that their intersection is also a s-t mincut. Make algorithm which finds s-t min cut with minimal number of vertices in s.

I understand that there is need to check somehow all edges from the cut, but how to do it more effectively? As for the algorithm I see that the desicion is to find intersection of all min cuts, but can't understand how to find all min cuts( with one I have no problems)

I'd be very glad to get some help with it.

Thank you.

Upvotes: 0

Views: 3771

Answers (1)

I'm a shark
I'm a shark

Reputation: 51

Clearly homework, so here's a hint. Prove that, given a max flow, an s-t cut is minimum if and only if its capacity with respect to the residual network is zero. The nice thing about zero-capacity cuts is that they're the ones whose outgoing arcs all have capacity zero, which is a local property instead of a global one. From here, the proof of the intersection property is a couple lines, and the algorithm is straightforward as well (it doesn't compute "all" s-t min cuts).

Upvotes: 5

Related Questions