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.

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 8 E V and a medical facility at t EVis 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 E V, which can be thought of as a node capacity of that city, is c 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: fen(v) s cu 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