Maximum matching in bipartite and non-bipartite graphs

The maximum matching problem Let G = (V;E) be an undirected graph. A set M E is a matching if no two edges in M have a common vertex. A vertex v is matched by M if it is contained is an edge of M, and unmatched otherwise. In the maximum matching problem we are asked to nd a matching M of maximum size

in a given input graph G = (V;E). The maximum matching problem in bipartite graphs can be easily reduced to a maximum ow problem in unit graphs that can be solved in O(mpn) time using Dinic’s algorithm. We present the original derivation of this result, due to Hopcroft and Karp [HK73]. The maximum matching problem in general, not necessarily bipartite, graphs is more challenging. We present here a classical algorithm of Edmonds [Edm65] for solving the problem and discuss its e cient implementation. 2 Alternating and augmenting paths De nition 2.1 (Alternating paths and cycles) Let G = (V;E) be a graph and let M be a matching in M. A path P is said to be an alternating path with respect to M if and only if among every two consecutive edges along the path, exactly one belongs to M. An alternating cycle C is de ned similarly. Some alternating paths and an alternating cycle are shown in Figure 2. We use the convention that edges that belong to a matching M are shown as thick edges, while edges not belonging to M are shown as thin edges. School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. E{mail: zwick@tau.ac.il 1 Figure 1: Matchings in a simple graph Figure 2: Alternating paths and cycles De nition 2.2 (Symmetric di erence) If A and B are sets, we let A B = (A B)[(B A) be their symmetric di erence. The following lemma is now obvious. Lemma 2.3 If M is a matching and P is an alternating path with respect to M, where each endpoint of P is either unmatched by M or matched by the edge of P touching it, then M P is also a matching. Note that if P starts and ends in vertices unmatched by M (e.g., the top path in Figure 2), then jM Pj=jMj+ 1, i.e., M P is a larger matching. If P starts with an edge that does not belong to M and ends with an edge of M (e.g., the middle path in Figure 2), thenjM Pj=jMj. Finally, if P starts and ends with edges of M (see the bottom path in Figure 2), then jM Pj=jMj 1. De nition 2.4 (Augmenting paths) An augmenting path P with respect to a matching M is an alternating path that starts and ends in unmatched vertices. We have seen above that...

Website: www.cs.tau.ac.il | Filesize: -
No of Page(s): 13
Download Maximum matching in bipartite and non-bipartite graphs.pdf