Due Friday, Mar 27th in class.

Submissions: Please submit your printed or hand written solutions in class. If you have a compelling reason for not being able to attend that particular class, please email your submissions to the instructor or the TA.

Policy: Write your own solutions independently; include the names of anyone you discussed the problems with.

1. Let be an undirected graph with capacities on each edge . Let be two of its vertices. Let be the set of paths in and be the subsets of edges that are cuts. Show that

2. Show that in any graph with a valid flow on its edges,

(a) The flow from to can be decomposed into paths and simple cycles (no repeated vertices). In other words, each path from to carries a flow of value on its edges and each cycle carries a flow of value on its edges. The total flow on an edge is equal to the sum of the flow values of all paths and cycles containing the edge.

(b) Given capacities on the edges, there is a maximum flow with no cycles.

3. Let be a closed convex set in . Show that for any point not in , there is a vector and a real value s.t. and for every .

4. Write a linear program for the maximum flow problem in a directed graph, using one flow variable for every path from the source s to the sink t (so the number of variables could be exponential in the size of the graph). Then write the dual of the program and interpret the variables, constraints and objective value of the dual.

5. (Bonus) Write an LP for the maxflow problem using flow variables, one for each edge. Write the dual and argue that it represents a minimum s-t cut.

I think I have found a counterexample for number 3…. Should I put it here or email to one of the instructors?

Include it in your homework submission.

Could someone please clarify what is meant in question 1. The first sentence is really confusing to me.

For example, let G = (V, E) be an undirected graph with vertices V = {A, B, C} and edges E = {(A, B), (B, C), (C, A)}; that is, G is a 3-cycle. And let c_(A, B) = 5, let c_(B, C) = 10, and let c_(C, A) = 15 just for the sake of example. So the capacity on edge (A, B) is 5, on (B, C) is 10, and on edge (C, A) is 15. Here is a picture: http://i.imgur.com/GsIGzOl.png

And a picture too! Thanks man. That helps tons.

Is anyone able to translate what the last part means? Is the LHS say the capacity on the edge of minimum capacity within the s-t path that has the highest sum of capacities out of all s-t paths?

Chris: there’s no sum — the LHS is the maximum, over all s-t paths, of the minimum edge on each s-t path.

Are the s-t paths in P edge disjoint? And thank you for clarifying.

No, they might not be. There is some possibly large set of s-t paths some of which might share edges. For each path, there is a minimum edge capacity. The LHS is the maximum of all these minimum capacities.

It’s minor but the LaTeX for problems 4 and 5 seems to not be working.

I’m having a lot of trouble with question 3. If you have a situation like in this image http://i.imgur.com/04TW65j.png , where could w be so as to satisfy the constraints on t?