CODEWITHSUNDEEP
algorithmgraph
RookieCookie
RookieCookie

Reputation: 312

Max Flow/Minimum Cut - Flow after removing K edges algorithm

I was asked to develop an algorithm for the following problem :

Given :

  1. A flow network G whose edges have maximum capacity of 1
  2. G's maximum flow |F|
  3. A positive integer K

Delete exactly K edges so that the flow of the network is minimized.

My thoughts/algorithm :

  1. If K is greater than or equal to |F| delete ALL of the edges that cross G's Minimum cut and if K is still greater than zero delete random edges and the new max flow is zero

  2. If K is equal to |F| delete ALL of the edges that cross G's Minimum cut and the new max flow is zero

  3. If K is less than |F| delete K of the edges that cross G's Minimum cut and the new max flow is |F|-K

I am in need of some validation as the Max Flow/Min Cut is new to me. Lastly the intuition behind the Max Flow/Min Cut that i got is that the Min (Source,Sink) cut works as a "bottleneck" to the maximum flow we can push in the network.Is that right?

Upvotes: 0

Views: 3304

Answers (1)

Photon
Photon

Reputation: 2777

Yes min cut is "bottleneck" for flow, also |Min-Cut| = Max-flow. There's tons of proofs online if you're interested (it's known as max-flow min cut theorem).

For your algorithm there's no need to delete random edges in step one, deleting one edge from min-cut reduces max-flow by the flow that goes through that edge (in this case 1 cause all weights are 1 according to statement).

So solution is just:

  1. Find any Min-cut
  2. Delete min(K, |Min-cut| edges from the graph)

Finding Min-Cut can be done very easily:

  1. Construct residual flow graph
  2. Run any max-flow algorithm on it (Ford-Fulkerson, Bellman-Ford, etc)
  3. Now do BFS from source node, only go through edges where flow value is less than capacity
  4. Now all edges that go from visited node to unvisited node form a min-cut

Upvotes: 3

Related Questions