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.