Question

Given a graph G = (V,E), the source-sink pair (s,t) and capacity of edges {C_e ≥ 0 | e ∈ E}, design a polynomial-time algorithm to find a set of edges S, such that for every edge e ∈ S, increasing C_e will lead to an increase of max-flow value between s and t. Show the correctness of your algorithm.

Answer 1

Consider the Ford-Fulkerson algorithm, which creates residual graphs after sending some flow from s to t, and then stops when s and t become disconnected in the residual graph.

Hence, in the final residual graph, any path from s to t contains at least one edge which is being used for its full capacity.

Now, let the set of vertices which are reachable from s in the final residual graph be and the final set of vertices reacheable from t in the final residual graph be . Then any edge will be such that if the capacity of this edge is increased, then the max flow will increase as well.

To see why this is the case, let the capacity of such an edge be increased. Then the flow being sent across this edge is not using its full capacity anymore, hence this edge will connect s to t in the residual graph. This further implies that the residual graph allows another step of the Ford-Fulkerson algorithm, hence the flow can be increased by at least 1.

Thus, the algorithm simple outputs all edges between and , after running Ford-Fulkerson algorithm to find the maximum flow. The algorithm is correct as argue above.

The algorithm takes polynomial time as Ford-Fulkerson algorithm takes polynomial time. Then, finding can be done using any reachability algorithm, like Dijkstra's algorithm, which also runs in polynomial time. Then, the algorithm simply finds all edges between the two sets, which is easily doable in polynomial time.

Comment in case of any doubts.