CODEWITHSUNDEEP
algorithmgraphgraph-algorithmedges
realmatt
realmatt

Reputation: 43

Computing Min-Cut of a Graph with No Reverse Edges

I know you can use a Max-Flow algorithm like Ford-Fulkerson and find a Min-Cut with the Max-Flow/Min-Cut theorem. However, this is not exactly the type of Min-Cut I need to compute.

I want to find the Min-Cut of graph G into sets S and T, where there are no edges from T to S.

This example graph finds a min-cut (of magnitude 250), but the result has an edge from T to S (the red one).

enter image description here

Does anyone know if there's an existing algorithm to solve this? Or if there's a way to modify my flow network so I can use something like Ford-Fulkerson?

Upvotes: 4

Views: 359

Answers (1)

Niklas B.
Niklas B.

Reputation: 95308

I believe this should work: For every edge, add a reverse edge with infinite capacity. That way if the min-cut is finite, original edges can only go from S to T, not the other way round.

Upvotes: 1

Related Questions