HW 4

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 G=(V,E) be an undirected graph with capacities c_e on each edge e \in E. Let s,t be two of its vertices. Let {\bf P} be the set of s-t paths in G and {\bf C} be the subsets of edges that are s-t cuts. Show that

\max_{P \in {\bf P}} \min_{e \in P} c_e = \min_{C \in {\bf C}} \max_{e \in C} c_e

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

(a) The flow from s to t can be decomposed into s-t paths and simple cycles (no repeated vertices). In other words, each path P from s to t carries a flow of value f_P on its edges and each cycle C carries a flow of value f_C 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 s-t flow with no cycles.

3. Let K be a closed convex set in {\bf R}^n. Show that for any point b not in K, there is a vector w \in {\bf R}^n and a real value t s.t. w^Tb \le t and w^Tx > t for every x \in K.

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.

Advertisements

11 Comments

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

    Reply

    1. 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

      Reply

      1. 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?

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

      3. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s