Solve the following by reducing to the original max-flow problem. In other words, explain how to
solve the new flow variant problem using an algorithm for solving max-flow as a black-box. Explain
how to take an input for the new problem and define an input for the original max-flow problem.
Then given a max-flow f ∗to this input you just defined, explain how to get the solution to the new
problem. You should describe your design in words; no pseudocode. Justify the correctness of your
design and state and justify the runtime.

(a) (Vertex capacity) You are given a network {G = (V, E), ce, cv, s, t} where cv > 0, v ∈ V is de-
fined as the capacity of each vertex and bounds the amount of flow that can enter the corresponding
vertex. Your task is to find a max-flow that satisfies this new constraint, on top of the conservation
of flow and the edge capacity constraints.

(b) (Disjoint paths) Given a directed graph G = (V, E), and vertices s, t ∈ V , design an algorithm
that outputs the maximum number of vertex-disjoint paths from s to t. Describe your design with
words (no pseudocode), justify its correctness and state and analyse its runtime.

Solution

Step-by-step explanation

{'enhancedContentMarkup': '\n\n\n\n \n \n

General guidance

\n\n

The answer provided below has been developed in a clear step by step manner.

\n

Show more

\n\n\n \n

\n First Step | All Steps | Answer Only\n \n

\n\n \n \n

Step-by-step

\n\n

\n

Step 1 of 1

\n

\n

GIVEN THAT:

A.

THERE ARE MANY SOURCES AND MANY SINKS:

1. This is quite simple situation of multiple source(let s1, s2,..,sx be the source vertices) and multiple sink(t1,t2,...,ty be the sink vertices).

2. To get the equivalent flow using only source and single sink create two vertices s and t for source and sink respectively and from vertex s create edge towards all the source vertices (i.e. towards s1, s2,...,sx) with infinite capacity and from every sink vertices (i.e. t1, t2,..,ty) create an edge with infinite capacity towards vertex t.

3. Now compute max flow from s to t in the reduced graph with s as the only source and t as the single sink. This will give the equivalent max-flow as it would be in the original graph.

4. The reason behind correctness of our approach is that since multiple sources relate to infinite capacity edges from vertex s, so still infinite flow can enter these sources and hence the situation is equivalent as if there would be multiple sources.

5. Similarly infinite capacity edges are connected from multiple sinks to t, so output of multiple sinks can simply be pass out from t.

6. Hence flow across the edges in original graph will be same as flow across the edges in reduced graph, and sum of flow starting from multiple source (as well as ending at multiple sink) will be equal to total flow starting from t(as well as ending at t).

B.

EACH VERTEX ALSO HAS A CAPACITY:

1. Situation is amazingly simple. For every vertex v, let c(v) be the capacity of flow that can pass through vertex v.

2. Then we will reduce this network flow graph G with vertex capacity to equivalent network flow graph G\' without vertex capacity by creating two vertices v1 and v2 for every vertex v in graph G, where the flow entering into v will now enter into v1 and flow leaving from v will now leave from v2 and from vertex v1 to v2, there will be an edge with capacity c(v) so that at most c(v) can pass through this edge.

3. Now by adding edge with capacity c(v) from v1 to v2, we have ensured that not more than c(v) can enter into v1 and hence not more than c(v) flow can leave v2 and hence by this way we will be able to maintain vertex flow capacity constrained.

4. Remaining flow through original edges will be same as that in the reduced graph as well as total flow f will be equal to max-flow obtained in the reduced graph.

Explanation

Please refer to solution in this step.

\n\n

Answer

\n \n

Thank you

--------------

\n \n

\n

\n\n \n\n\n\n\n \n\n

Answer only

\n

Thank you

--------------

\n\n\n\n \n\n'}