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