Solve the following by reducing to the original max-flow problem

Subject:Computer SciencePrice:9.82 Bought3

Share With

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.