Given a graph G = (V,E), the source-sink pair (s,t) and capacity of edges {C_e ≥...

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.

Expert Solution

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.

venereology answered 1 year ago

Let G = (V, E) be a directed graph, with source s ∈ V, sink t...

Let G = (V, E) be a directed graph, with source s ∈ V, sink t ∈ V, and nonnegative edge capacities {ce}. Give a polynomial-time algorithm to decide whether G has a unique minimum s-t cut (i.e., an s-t of capacity strictly less than that of all other s-t cuts).

You are given a directed graph G(V,E) with n vertices and m edges. Let S be...

You are given a directed graph G(V,E) with n vertices and m edges. Let S be the subset of vertices in G that are able to reach some cycle in G. Design an O(n + m) time algorithm to compute the set S. You can assume that G is given to you in the adjacency-list representation.

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}. Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.

If G = (V, E) is a graph and x ∈ V , let G \...

If G = (V, E) is a graph and x ∈ V , let G \ x be the graph whose vertex set is V \ {x} and whose edges are those edges of G that don’t contain x. Show that every connected finite graph G = (V, E) with at least two vertices has at least two vertices x1, x2 ∈ V such that G \ xi is connected.

Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether...

Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether G contains a clique of size m or more. (A clique of size k in a graph is its complete subgraph of k vertices.) Determine, for a given graph G = V,E and a positive integer m ≤ |V |, whether there is a vertex cover of size m or less for G. (A vertex cover of size k for a graph G =...

You are given an undirected graph G = ( V, E ) in which the edge...

You are given an undirected graph G = ( V, E ) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight from 1 to W, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(E+V) time.

Given an undirected graph G=(V, E) with weights and a vertex , we ask for a...

Given an undirected graph G=(V, E) with weights and a vertex , we ask for a minimum weight spanning tree in G where is not a leaf (a leaf node has degree one). Can you solve this problem in polynomial time? Please write the proof.

Indicate the net charge for the peptide, C-H-A-V-E-C-A-R-R-I-S-T-H-E-G-R-E-A-T-E-S-T, at the given pH values: (a) pH 1,...

Indicate the net charge for the peptide, C-H-A-V-E-C-A-R-R-I-S-T-H-E-G-R-E-A-T-E-S-T, at the given pH values: (a) pH 1, net charge: (b) pH 5, net charge: (c) pH 8, net charge: (d) pH 14, net charge:

# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0...

# Problem Description Given a directed graph G = (V,E) with edge length l(e) > 0 for any e in E, and a source vertex s. Use Dijkstra’s algorithm to calculate distance(s,v) for all of the vertices v in V. (You can implement your own priority queue or use the build-in function for C++/Python) # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives three numbers `n`,`m` and `s`(1 <=...

# Problem Description Given a directed graph G = (V, E), find the number of connected...

# Problem Description Given a directed graph G = (V, E), find the number of connected components in G. # Input The graph has `n` vertices and `m` edges. There are m + 1 lines, the first line gives two numbers `n` and `m`, describing the number of vertices and edges. Each of the following lines contains two numbers `a` and `b` meaning there is an edge (a,b) belong to E. All the numbers in a line are separated by...

Question