2. In this problem we will derive the max flow min cut theorem using linear program duality. Given a flow network (V, E, c), here is a linear program that solves for the max flo max (s,v) VEV VEV fe 20, Ve e E. (Note that the formulation is slightly different from the flow definition we gave, which allowed negative flows. They are largely equivalent. The version we gave talk about the "net" flow along an edge. For example, one may think of a flow of 2 units along (u, v) and another flow of 1 unit along (v,u); in this formulation, we simply have f(u,v) -2 and f(e.u) -1, whereas in our former formulation we would represent the net flow from u to v, i.e., f(u,v)-2 and f(e.u) 2-1=1 1 21. In this problem we use (1 (a) (5 points) Write the dual of this linear program. Can you convert your program so that there is a variable ye for each edge and an xu for each vertex u E Vs,t!? (When doing so, your LP most likely is not in the canonical form.) (b) (3 points) Show that any solution to the dual LP satisfies the following property: for any directed path from s to t in the network, the sum of the ye values along the path (c) (3 points) Show that any s-t cut in the network can be translated into a dual feasible (Convince yourself that by the strong duality theorem, the above steps show the max flow must be at least 1. solution whose cost is exactly the capacity of that cut. min cut theorem. You do not have to write down this last argument. 2. In this problem we will derive the max flow min cut theorem using linear program duality. Given a flow network (V, E, c), here is a linear program that solves for the max flo max (s,v) VEV VEV fe 20, Ve e E. (Note that the formulation is slightly different from the flow definition we gave, which allowed negative flows. They are largely equivalent. The version we gave talk about the "net" flow along an edge. For example, one may think of a flow of 2 units along (u, v) and another flow of 1 unit along (v,u); in this formulation, we simply have f(u,v) -2 and f(e.u) -1, whereas in our former formulation we would represent the net flow from u to v, i.e., f(u,v)-2 and f(e.u) 2-1=1 1 21. In this problem we use (1 (a) (5 points) Write the dual of this linear program. Can you convert your program so that there is a variable ye for each edge and an xu for each vertex u E Vs,t!? (When doing so, your LP most likely is not in the canonical form.) (b) (3 points) Show that any solution to the dual LP satisfies the following property: for any directed path from s to t in the network, the sum of the ye values along the path (c) (3 points) Show that any s-t cut in the network can be translated into a dual feasible (Convince yourself that by the strong duality theorem, the above steps show the max flow must be at least 1. solution whose cost is exactly the capacity of that cut. min cut theorem. You do not have to write down this last argument