DAA

372 Iterative Improvement b. Prove that for any flow in a network and any cut in it, the value of the flow is equal to the flow across the cut (see equality (10.12)). Explain the relationship between this property and equality (10.9). 7. a. Express the maximum-flow problem for the network in Figure 10.4 as a linear programming problem. b. Solve this linear programming problem by the simplex method. 8. As an alternative to the shortest-augmenting-path algorithm, Edmonds and Karp [Edm72] suggested the maximum-capacity-augmenting-path algorithm, in which a flow is augmented along the path that increases the flow by the largest amount. Implement both these algorithms in the language of your choice and perform an empirical investigation of their relative efficiency. 9. Write a report on a more advanced maximum-flow algorithm such as (i) Dinitz’s algorithm, (ii) Karzanov’s algorithm, (iii) Malhotra-Kamar- Maheshwari algorithm, or (iv) Goldberg-Tarjan algorithm. 10. Dining problem Several families go out to dinner together. To increase their social interaction, they would like to sit at tables so that no two members of the same family are at the same table. Show how to find a seating arrangement that meets this objective (or prove that no such arrangement exists) by using a maximum-flow problem. Assume that the dinner contingent has p families and that the ith family has ai members. Also assume that q tables are available and the j th table has a seating capacity of bj . [Ahu93] 10.3 Maximum Matching in Bipartite Graphs In many situations we are faced with a problem of pairing elements of two sets. The traditional example is boys and girls for a dance, but you can easily think of more serious applications. It is convenient to represent elements of two given sets by vertices of a graph, with edges between vertices that can be paired. A matching in a graph is a subset of its edges with the property that no two edges share a vertex. A maximum matching—more precisely, a maximum cardinality matching—is a matching with the largest number of edges. (What is it for the graph in Figure 10.8? Is it unique?) The maximum-matching problem is the problem of finding a maximum matching in a given graph. For an arbitrary graph, this is a rather difficult problem. It was solved in 1965 by Jack Edmonds [Edm65]. (See [Gal86] for a good survey and more recent references.) We limit our discussion in this section to the simpler case of bipartite graphs. In a bipartite graph, all the vertices can be partitioned into two disjoint sets V and U , not necessarily of the same size, so that every edge connects a vertex in one of these sets to a vertex in the other set. In other words, a graph is bipartite if its vertices can be colored in two colors so that every edge has its vertices colored in different colors; such graphs are also said to be 2-colorable. The graph in Figure 10.8 is bipartite. It is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length. We will assume for the rest of this section that

10.3 Maximum Matching in Bipartite Graphs 373 V1 2 3 4 U5 6 7 8 FIGURE 10.8 Example of a bipartite graph. the vertex set of a given bipartite graph has been already partitioned into sets V and U as required by the definition (see Problem 8 in Exercises 3.5). Let us apply the iterative-improvement technique to the maximum- cardinality-matching problem. Let M be a matching in a bipartite graph G = V , U, E . How can we improve it, i.e., find a new matching with more edges? Obviously, if every vertex in either V or U is matched (has a mate), i.e., serves as an endpoint of an edge in M, this cannot be done and M is a maximum matching. Therefore, to have a chance at improving the current matching, both V and U must contain unmatched (also called free) vertices, i.e., vertices that are not inci- dent to any edge in M. For example, for the matching Ma = {(4, 8), (5, 9)} in the graph in Figure 10.9a, vertices 1, 2, 3, 6, 7, and 10 are free, and vertices 4, 5, 8, and 9 are matched. Another obvious observation is that we can immediately increase a current matching by adding an edge between two free vertices. For example, adding (1, 6) to the matching Ma = {(4, 8), (5, 9)} in the graph in Figure 10.9a yields a larger matching Mb = {(1, 6), (4, 8), (5, 9)} (Figure 10.9b). Let us now try to find a matching larger than Mb by matching vertex 2. The only way to do this would be to include the edge (2, 6) in a new matching. This inclusion requires removal of (1, 6), which can be compensated by inclusion of (1, 7) in the new matching. This new matching Mc = {(1, 7), (2, 6), (4, 8), (5, 9)} is shown in Figure 10.9c. In general, we increase the size of a current matching M by constructing a simple path from a free vertex in V to a free vertex in U whose edges are alternately in E − M and in M. That is, the first edge of the path does not belong to M, the second one does, and so on, until the last edge that does not belong to M. Such a path is called augmenting with respect to the matching M. For example, the path 2, 6, 1, 7 is an augmenting path with respect to the matching Mb in Figure 10.9b. Since the length of an augmenting path is always odd, adding to the matching M the path’s edges in the odd-numbered positions and deleting from it the path’s edges in the even-numbered positions yields a matching with one more edge than in M. Such a matching adjustment is called augmentation. Thus, in Figure 10.9, the matching Mb was obtained by augmentation of the matching Ma along the augmenting path 1, 6, and the matching Mc was obtained by augmentation of the matching Mb along the augmenting path 2, 6, 1, 7. Moving further, 3, 8, 4, 9, 5, 10 is an augmenting path for the matching Mc (Figure 10.9c). After adding to Mc the edges (3, 8), (4, 9), and (5, 10) and deleting (4, 8) and (5, 9), we obtain the matching Md = {(1, 7), (2, 6), (3, 8), (4, 9), (5, 10)} shown in Figure 10.9d. The

374 Iterative Improvement V1 2 3 4 5 U6 789 10 1 (a) 5 Augmenting path: 1, 6 234 6 7 8 9 10 (b) Augmenting path: 2, 6, 1, 7 12345 6 7 8 9 10 (c) Augmenting path: 3, 8, 4, 9, 5, 10 12345 6 7 8 9 10 (d) Maximum matching FIGURE 10.9 Augmenting paths and matching augmentations.

10.3 Maximum Matching in Bipartite Graphs 375 matching Md is not only a maximum matching but also perfect, i.e., a matching that matches all the vertices of the graph. Before we discuss an algorithm for finding an augmenting path, let us settle the issue of what nonexistence of such a path means. According to the theorem discovered by the French mathematician Claude Berge, it means the current matching is maximal. THEOREM A matching M is a maximum matching if and only if there exists no augmenting path with respect to M. PROOF If an augmenting path with respect to a matching M exists, then the size of the matching can be increased by augmentation. Let us prove the more difficult part: if no augmenting path with respect to a matching M exists, then the matching is a maximum matching. Assume that, on the contrary, this is not the case for a certain matching M in a graph G. Let M∗ be a maximum matching in G; by our assumption, the number of edges in M∗ is at least one more than the number of edges in M, i.e., |M∗| > |M|. Consider the edges in the symmetric difference M ⊕ M∗ = (M − M∗) ∪ (M∗ − M), the set of all the edges that are either in M or in M∗ but not in both. Note that |M∗ − M| > |M − M∗| because |M∗| > |M| by assumption. Let G be the subgraph of G made up of all the edges in M ⊕ M∗ and their endpoints. By definition of a matching, any vertex in G ⊆ G can be incident to no more than one edge in M and no more than one edge in M∗. Hence, each of the vertices in G has degree 2 or less, and therefore every connected component of G is either a path or an even-length cycle of alternating edges from M − M∗ and M∗ − M. Since |M∗ − M| > |M − M∗| and the number of edges from M − M∗ and M∗ − M is the same for any even-length cycle of alternating edges in G , there must exist at least one path of alternating edges that starts and ends with an edge from M∗ − M. Hence, this is an augmenting path for the matching M, which contradicts the assumption that no such path exists. Our discussion of augmenting paths leads to the following general method for constructing a maximum matching in a bipartite graph. Start with some initial matching (e.g., the empty set). Find an augmenting path and augment the current matching along this path. When no augmenting path can be found, terminate the algorithm and return the last matching, which is maximum. We now give a specific algorithm implementing this general template. We will search for an augmenting path for a matching M by a BFS-like traversal of the graph that starts simultaneously at all the free vertices in one of the sets V and U, say, V . (It would be logical to select the smaller of the two vertex sets, but we will ignore this observation in the pseudocode below.) Recall that an augmenting path, if it exists, is an odd-length path that connects a free vertex in V with a free vertex in U and which, unless it consists of a single edge, “zigs” from a vertex in V to another vertex’ mate in U , then “zags” back to V along the uniquely defined edge from M, and so on until a free vertex in U is reached. (Draw augmenting paths for the matchings in Figure 10.9, for example.) Hence, any candidate to be such a