USA: +1 (725) 712-1730 
Sign in
1.( Node-capacitated networks 2-page limit – your solutions should fit on two sides of 1 page)
A zombie infestation on earth is threatening the population of all our cities. The virus originated mysteriously at a site located at s ∈ V and a medical facility at t ∈ V is working on a cure at the moment. You have to stop the virus from spreading across a network of cities, represented by a directed graph G = (V,E), between s and t because the facility at t is your only chance at saving the planet. The cost of cutting off all possible transportation out of a single city v ∈ V, which can be thought of as a node capacity of that city, is cv ≥ 0. You can define a flow f in this network, given that the flow though a node v is defined as fin(v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and also the following constraints: fin(v) ≤ cv for all nodes. You have to find an s-t maximum flow through this network, cutting which will solve your problem in polynomial time. Define an s-t cut for such a network, and show that the analogue of the Max-Flow Min-Cut Theorem holds true.
To organize your answer better break it into parts as follows:
(a) Give an algorithm for maximum flows in node-capacitated networks of this kind. Pay close attention to the argument of correctness of your algorithm.
[Hint: One way to give an algorithm for this problem is to run Ford-Fulkerson on a modified version (say G′ = (V ′, E′)) of the original graph G, in which each vertex in V corresponds to two vertices (call them vin and vout) in V ′. The graph G′ should have an edge e′ for every edge e in E along with some additional edges.]
(b) Define an analogue of an s-t cut in a node-capacitated network, and define the “capacity” of your object.
(c) Explain why the max-flow min-cut theorem holds for your analogue.
If it is easier, you may want to prove correctness of your algorithm at the same time as you prove your max-flow/min-cut theorem.
Solution guidelines For problems that require you to provide an algorithm, you must give the following:
1. a precise description of the algorithm in English and, if helpful, pseudocode,
2. a proof of correctness,
3. an analysis of running time and space.
Expert Answer
1.
Maxflow:
Main idea: find valid flow paths until there is none left, and add them up.
Proof:
- Take a maximum flow f ⋆ and “subtract” our flow f. It is a valid flow of positive total flow. By the flow decomposition, it can be decomposed into flow paths and circulations. flow paths must have been found by Contradiction of Ford-Fulkerson.
- We don’t need to maintain the amount of flow on each edge but work with capacity values directly
- If f amount of flow goes through u → v, then: – Decrease c(u → v) by f – Increase c(v → u) by f
- Set ftotal = 0
- Repeat until there is no path from s to t: – Run DFS from s to find a flow path to t – Let f be the minimum capacity value on the path – Add f to ftotal – For each edge u → v on the path: ◮ Decrease c(u → v) by f Increase c(v → u) by f
Analysis:
- Assumption: capacities are integer-valued
- Finding a flow path takes Θ(n + m) time
- We send at least 1 unit of flow through the path
- If the max-flow is f ⋆ , the time complexity is O((n + m)f ⋆ ) – “Bad” in that it depends on the output of the algorithm
2.
s-t cut value is an upper bound on v(f). Given a network N, the max-flow problem is to find a feasible flow with the maximum possible value.
max f f easible v(f) ≤ min (A,B) c(A, B). We will show that equality is in fact attained by the max-flow and min-cut values.
3.
We construct a new graph H where for every vertex v in G, we have two vertices vi and vo. There is an edge from vi to vo of capacity cv. If the graph G has an edge (u, v), then we add an edge (uo, vi) in H of infinite capacity. Now notice that any flow in H entering vi must go through the edge (vi , vo) and so the total amount of flow entering vi (or leaving vo) cannot exceed cv. Now it is easy to check that a flow of value v in G results in a flow of the same value in H and vice-versa
