HW7: Flow

1. Given a graph $G = (V,E)$ with integer capacities $C_e$ on its edges, and two special vertices $s,t \in V$ critical edge $e$ of $G$ is an edge with the property that increasing its capacity would increase the value of the maximum flow. Give an efficient algorithm to identify all critical edges of a graph.
2. 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$.
3. Given an undirected graph $G=(V,E)$ with non-negative integer capacities on edges, give an efficient algorithm to find the global min-cut, i.e., the smallest capacity set of edges whose removal disconnects the graph.
4. Let $G=(V,E)$ be a directed graph with capacities on its edges and two special vertices $s,t$. The capacity of a directed path from $s$ to $t$ is the smallest of the capacities of edges on the path. Give an efficient algorithm to find a path from $s$ to $t$ of maximum capacity.