CSE 421 Assignment #6
Autumn 2012

Due: Friday, November 16, 2012.

Reading Assignment: Kleinberg and Tardos Chapter 7 (sections 7.1, 7.2, 7.3, 7.5, 7.6, 7.11).

Problems: (see the Grading Guidelines before answering)

1. Kleinberg and Tardos, Chapter 6, Problem 12, page 323-324.

2. Kleinberg and Tardos, Chapter 7, Problem 8, page 418.

3. Kleinberg and Tardos, Chapter 7, Problem 13, pages 420-421.

4. Extra credit: We saw how repeatedly augmenting along shortest paths (given by a BFS each time) produced a better runtime analysis for general network flow. In this problem you will do something similar in the special case of finding a maximum matching in a bipartite graph G=(V,E) where the two sides of V are X and Y, n=|V|, m=|E|. The idea here will be to augment along many shortest paths at the same time. In order for this to work, the paths better not share any edges. Your algorithm will add the slightly stronger condition that the paths do not share any vertices and will include as many shortest paths as possible at each step.

   More precisely, at each round the new algorithm will simultaneously augment along all paths in some maximal set P_short of vertex-disjoint shortest augmenting paths in the flow graph associated with the bipartite matching problem. (In other words, if d_f(s,t) is the length of the shortest augmenting path in the residual graph G_f then every path in P_short has length d_f(s,t) and any other st-path of length d_f(s,t) shares at least one vertex other than s and t with a path in P_short.)

   1. Show how to find a set P_short and do all the augmentations on its paths to get a flow f' in time O(m+n).
   2. Prove that d_f'(s,t) ≥ d_f(s,t)+2.
   3. Given two matchings M and M' on graph G we can define the symmetric difference, M Δ M', of M and M' to be the graph consisting of edges that occur in exactly one of the two matchings. M Δ M' consists of a collection of vertex-disjoint paths and cycles (why?). Show that if M' is a maximum matching and flow f corresponds to a matching M of G then
      1. M Δ M' contains exactly |M'|-|M| vertex-disjoint odd-length paths.
      2. Any path of odd length k in M Δ M' corresponds to an augmenting path of length k+2 in G_f.
      3. Use these two properties to prove that once all augmenting paths in G_f. are of length at least k+2 then at most n/k additional augmentations will produce a maximum flow (and hence maximum matching).
   4. Use the above analysis with a suitable value of k to show that this algorithm computes a maximum matching in O(n^1/2m) time.