Question: Suppose you are given a flow network where each edge has the same capacity, that is, a directed graph G = (V, E) with a
Suppose you are given a flow network where each edge has the same capacity, that is, a directed graph G = (V, E) with a source node s and sink node t, such that ce = j for all e E, where j is an integer constant greater than zero. You can reduce the maximum s-t flow by removing edges. Given k < |E|, find the k edges whose removal from the graph reduces the maximum s-t flow the most. That is, describe the algorithm that takes a flow network G = (V, E) and a number k, and returns the set of edges E' such that E' E and |E'| = k, and the maximum s-t flow in (V, E E') is as small as possible. Your algorithm should be polynomial in |V| + |E|, the number of vertices and edges in the graph. You can assume you have the Ford-Fulkerson algorithm to build on.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
