An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs HAROLD N. GABOW Univer~ty of Colorado, Boulder, Colorado ABSTRACT. A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding a maximum matching The computation time is proportional to V*, where V is the number of vertices; previous implementatmns of Edmonds' algorithm have computation time proportional to V4. The implementation is based on a system of labels that e n c o d e s the structure of alternating paths. KEYWORDSANDPHRASES; graph algorithm, matching on a graph, maximum matching, augmenting path, labeling technique CR CATEGORIES: 5.25, 5.32, 5.41 1. Introduction The problem of finding a maximum matching on a graph has applications in operations research and integer programming. For example, the following is a maximum matching problem: I n a factory, a manager must divide his workers into teams of two. Certain teams are not allowed, because the workers are incompatible. Choose the greatest possible n u m b e r of teams of compatible workers. We present an algorithm for finding a maximum matching on a graph. If V is the number of vertices, the run time is proportional to V3. The space required is 4V words in addition to the space needed for the graph. The approach is a careful implementation of ideas presented by Edmonds [4]. His algorithm has run time proportional to V4 [4; 6, Erratum]. We improve this by eliminating the process of blossom expansion. Instead, we use a system of labels to store the structure of alternating paths. This approach is similar to labeling techniques in the matching algorithms of Balinski [1] and Witzgall and Zahn [13]. The former algorithm has run time proportional to V3, if a stack is used for vertex selection; the latter algorithm can be implemented in time proportional to V~, using techniques described here. However, both algorithms may label a vertex more than once in a search. This increases the r u n time and makes it difficult to generalize to other problems, such as finding a maximum weighted matching [13]. The present algorithm overcomes these difficulties [8]. Copyright © 1976, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM's copyright notice is given and that reference is made to the publication, to its date of issue, and t o t h e fact that reprinting privileges were granted by permission of the Association for Computing Machinery. This work was partially supported by the National Science Foundation Graduate Fellowship Program and the National Science Foundation under Grant G J-US0 at Stanford University, and by the National Science Foundation under Grant G J-660 at the University of Colorado. Author's address: Department of Computer Science,University of Colorado, Boulder, C O 80~02. Journal of the Assoc, iat/on for Computing Mschmery, Vol. 23, No 2, Aprd 1976, pp 221-234. 222 HAROLD N. GABOW l0 $ 8 FIG. 1 Matched graph G~ After summarizing definitions in Section 2, we state the algorithm in Section 3. A proof of correctness is given in Section 4. Section 5 discusses time and space bounds, and applications of the algorithm. '2. Preliminaries This section summarizes some well-known definitions and results. A graph G consists of a finite set of vertices and a finite set of edges. An edge is an (unordered) set of two distinct vertices. The edge containing vertices v and w is denoted vw (or wv). Vertices v and w are ad3acent. An adjacency list for v is a list of the vertices adjacent to v. A subgraph of G is a graph whose vertices and edges are in G. A graph is complete if any two vertices are adjacent. A walk W is a list of vertices (v~, v:, • - • , v~), where n > 1 and v,v~+l is an edge, for 1 < , < n. A walk is simple if no vertex occurs more than once in the list. A path is a simple walk. A cycle is a walk (vl, v2, - . - , v~, vl) such that n > 2 and (v~, v2, •. • , v, ) is simple. Let W = (vl, v2, • • , v~) and X = (v,+l, v,+2, . . . , v~) be walks. The reverse walk of W, denoted rev W , is ( v , , v ~ _ l , • • , vl). The concatenation of W and X, denoted W , X , is (vl , . • • , v, , v~+l , • • • , vz). For W * X to be a walk, it is necessary that v,v,+~ is an edge. For W . X to be a path, it is furl~her necessary that W and X are disjoint paths. A matching on a graph is a set of edges, no two of which share a vertex. A matched graph (G, M ) is a graph G with a matching M. A vertex v is matched if it is in some edge of the matching; otherwise v is unmatched. M is a m a x i m u m matching if no matching on G contains more edges than M. Figure I shows a matching on a graph G~ (matched edges are shown as wavy lines). Vertices 9 and 10 are unmatched. The matching is not maximum, since a matching with no unmatched vertices exists. An alternating path in a matched graph is a path (vl, • • • , v~) such that exactly one of every two edges v,_lv,'and v,v,+l is matched, for 1 < i < n. An augmentsng path is an alternating path whose ends v~ and v, are distinct unmatched vertices. If (vz, . . . , v~) is an augmenting path in (G, M ) , a new matching M ' is obtained b y replacing the matched edges v2,v2,+l, 1 < ~ < n , with the unmatched edges v2,-lv2,, 1 < i < n. We say the matching M is augmented to M', since M ' contains one more edge t h a n M. I n Figure 1, (10, 1, 2, 3, 4, 8, 7, 6, 5, 9) is an augmenting path. Augmenting gives a maximum matching. Note that an augmenting path is simple. We cannot augment a matching with a non- A n Effwient Implementation of Edmonds' Algorithm 223 simple alternating walk. This is illustrated in Figure 1 by the walk (10, 1, 2, 3, 4, 8, 7, 4, 3, 9). "Augmenting" does not give ~t matching, since edges 47 and 48 become "matched." Augmenting paths are important for this reason: LEMMA (Berge). A matched graph (G, M ) has an augmenting path if and only ~f M is not maximum. PROOF. See [2, 4]. As a result, a maximum matching can be found by repeatedly searching for augmenting paths and augmenting the matching. The algorithms in [1, 2, 13] and the one presented here are organized in this way. 3. Statement of the Algorithm This section presents an algorithm, called E, for finding a maximum matching on a graph. First, the basic strategy and the data structures of E are described. Then Algorithm E is stated. An example of how E works is given. Finally, E is compared with Edmonds' algorithm. The algorithm begins by numbering the vertices and edges of the graph. Below we do not distinguish between a vertex v and its number; we denote both by v. We denote the number of an edge vw as n(vw). Algorithm E constructs a number of matchings, the last of which is maximum. A matching is stored in the array M A T E . This array has an entry for each vertex. If v and w are vertices, edge vw is matched if M A T E ( v ) = w and M A T E ( w ) = v. Algorithm E begins with all vertices unmatched. It searches for an augmenting path. If such a path is found, the matching is augmented. The new matching contains one more edge than the previous one. Next E searches for an augmenting path for the new matching. This process is iterated. Eventually, E constructs a matching that has no augmenting path. This matching is maximum, by Berge's Lemma. Algorithm E searches for an augmenting path in the following way. First an unmatched vertex u is chosen. E scans edges to find alternating paths to u. A vertex v is called outer when E finds an alternating path from v to u that starts with a matched edge. Let such a path be P ( v ) = (v, vl, " . , u), so vvl is matched. E sets an entry in the L A B E L array for every outer vertex v. Path P(v) can be computed from L A B E L ( v ) . If an edge joining an outer vertex v to an unmatched vertex u' ~ u is scanned, E finds an augmenting path, ( u ' ) . P ( v ) = (u', v, vl, . . . , u). If no such edge is ever scanned, vertex u is not in an augmenting path. Figure 2 illustrates a search for an augmenting path to vertex u = 9. Figure 2(a) shows paths P ( 3 ) and P(7). Figure 2(b) shows the values stored by E. Now we explain these values. The L A B E L entry for an outer vertex is interpreted as either a start label, vertex label, or edge label. In Figure 2, eight vertices are outer. Each is labeled in one of these ways. The remaining vertex, 1, is nonouter. This means there is no Mternating path from 1 to 9 that starts with a matched edge. Nonouter vertices are drawn hollow in all figures in this paper. Now we describe the three label types. Start label. In the search for an augmenting path to the unmatched vertex u, u has a start label. This defines an alternating path, P ( u ) = (u). Vertex label. If outer vertex v has a vertex label, L A B E L ( v ) is the number of another outer vertex. Path P ( v ) is defined as (v, M A T E ( v ) ) , P ( L A B E L ( v ) ) . Using this definition, we compute P ( 8 ) : P ( 8 ) = (8, M A T E ( 8 ) ) . P ( L A B E L ( 8 ) ) = (8, 7).(4, a, 9) = (8, 7, 4, 3, 9). Edge label. If outer vertex v has an edge label, L A B E L ( v ) contains the number of an 224 HAROLD N. GABOW 'S v 2 Pl31-~( MATE(v) Label t y p e 1 2 nonouter 2 3 4 5 6 7 8 9 1 4 3 6 5 8 7 -- (o) LABEL(v) -- vertex edge vertex edge vertex edge vertex start 3 n (67) 9 n(67) 9 n(48) 4 -- FIRST(v) -- 1 0 0 0 0 0 0 0 (b) .Fi~ 2. Search values edge joining two outer vertices, LABEL(v) = n(xy). Path P(v) is defined in terms of paths P(x) and P(y). As an example, consider vertex 7, which has label n(48). Vertices 4 and 8 are outer, so there are alternating paths P ( 4 ) and P(8). Vertex 7 is in P(8). Let P(8, 7) denote the portion of P ( 8 ) from 8 to 7, i.e. P(8, 7) = (8, 7). Then P ( 7 ) is defined as the path (rev P (8, 7 ) ) *P (4), i.e. P ( 7 ) = (rev (8, 7 ) ) . ( 4 , 3, 9) = (7, 8, 4, 3, 9). Path P ( 3 ) is defined similarly. The label of vertex 3 is n(67). Since vertex 3 is in P ( 7 ) , path P ( 3 ) = (rev P(7, 3 ) ) . P ( 6 ) . E also uses an array FIRST. If v is an outer vertex, FIRST(v) is the first nonouter vertex in P(v). In Figure 2, the first nonouter vertex in P ( 2 ) is FIRST(2) = 1. Path P ( 7 ) does not contain any nonouter vertices, so FIRST(7) is set to 0, a d u m m y vertex. If edge 67 is removed, vertices' 2, 3, and 5 become nonouter, and FIRST(7) becomes 3. The array F I R S T speeds up the computation. Using FIRST, E finds the first nonouter vertex m P(v) with a table look-up. Without FIRST, this operation involves computing vertices m P(v) until a nonouter vertex is found. Thus F I R S T enables E to do in constant time what otherwise requires time proportional to V, the number of vertices. This speedup is crucial in achieving the O( V a) time bound. Now we state Algorithm E in detail. The vertices of the graph are numbered from 1 to V. E also uses a dummy vertex 0 for boundary conditions. The edges of the graph are stored in some standard manner, such as an adjacency matrix [9] or adjacency lists. For convenience we choose adjacency lists, using an approach described by Tarjan [11]. Let W be the number of edges in the graph. An array END has entries numbered from V -F 1 to V + 2W. For each edge, there are two consecutive entries, containing the numbers of the vertices in the 'edge. Thus edge vw is stored as the zth edge when E N D ( V + 2i - 1) = v and E N D ( V + 2,) = w. The edge number n(vw) is V + 2,. Thus, v and w can be easily computed from n(vw). There is an adjacency list for each vertex v. This list contains the numbers n(vw) of all edges containing v. The array END and the adjacency lists are referenced implicitly in the algorithm. See, for example, step E2, below. The M A T E array has an entry for each vertex. M A T E specifies a matching. If v, A n E f f w i e n t I m p l e m e n t a t i o n of E d m o n d s ' A l g o r i t h m 225 w ~ 0 a r e v e r t i c e s , M A T E ( v ) = 0 if v is u n m a t c h e d ; e d g e vw is m a t c h e d if M A T E ( v ) = w and MATE(iv) = v. T h e L A B E L a r r a y h a s a n e n t r y for e a c h v e r t e x . I n a g i v e n s e a r c h , a v e r t e x v is o u t e r if L A B E L ( v ) > O. I f v h a s a v e r t e x l a b e l , L A B E L ( v ) is a v e r t e x n u m b e r b e t w e e n 1 a n d V. I f v h a s a n e d g e label, L A B E L ( v ) is a n e d g e n u m b e r b e t w e e n V + 1 a n d V + 2 W . T h e s e c l a s s i f i c a t i o n s a r e u s e d i m p l i c i t l y in t h e a l g o r i t h m , i n t e s t s like " I f t h e v e r t e x is o u t e r , t h e n . . . . " See, for e x a m p l e , s t e p E 4 . T h e F I R S T a r r a y h a s a n e n t r y f o r e a c h v e r t e x . I n a g i v e n s e a r c h , if v is a n o u t e r v e r t e x then FIRST(v) is t h e f i r s t n o n o u t e r v e r t e x i n P ( v ) . T h e a l g o r i t h m is p r e s e n t e d b e l o w in a h i g h - l e v e l l a n g u a g e s i m i l a r t o K n u t h ' s [10]. E is t h e m a i n r o u t i n e . I t u s e s s u b r o u t i n e s L a n d R. E c o n s t r u c t s a m a x i m u m m a t c h i n g on a g r a p h It s t a r t s a search for an a u g m e n t i n g p a t h to each u n m a t c h e d vertex u. I t s c a n s edges of the graph, deciding to assign new labels or to a u g m e n t the matching E0. [Imtiahze.] R e a d t h e graph into adjacency lists, n u m b e r i n g t h e vertices 1 to V and t h e edges V -4- 1 to V + 2W. Create a d u m m y vertex 0 For 0 < i < V, s e t L A B E L ( u ) ~- --1, M A T E ( i ) ~- 0 (all vertices are nonouter a n d u n m a t c h e d ) Set u ~- 0 E l . [Find u n m a t c h e d vertex ] Set u ~-~ u + 1. If u > V, halt; M A T E c o n t a i n s a m a x i m u m m a t c h i n g Otherwise, if vertex u is m a t c h e d , repeat step E1 Otherwise (u is u n m a t c h e d , so assign a s t a r t label and begin a new search) s e t L A B E L ( u ) ~-- F I R S T ( u ) ~- O. E2 [Choose an edge ] Choose an edge xy, where x ]s an outer vertex. (An edge vw m a y be chosen twice in a s e a r c h - - o n c e with x = v, and once with x = w.) If no s u c h edge exists, go to E7. (Edges xy can be chosen m an arbitrary order. A posmble chome m e t h o d m " b r e a d t h - f i r s t " : a n o u t e r vertex x = xt is chosen, and edges x~y are chosen m succeeding executions of E2, when all s u c h edges have been chosen, the vertex x~ t h a t was labeled i m m e d i a t e l y after x~ is chosen, and the process is re. peated for x = x~. T h i s breadth-first m e t h o d requires t h a t A l g o r i t h m E m a i n t a i n a list of o u t e r vertices, xL, x~ • • • .) E3. [Augment the matching.l If y is u n m a t c h e d and y ¢ u, s e t M A T E ( y ) ~-- x, call R ( x , y): t h e n go to E7 (R completes the a u g m e n t along p a t h (y)*P(x)) E4. [Assign edge labels.] If y is outer, call L, then go to E2 (L assigns edge label n ( x y ) to n o n o u t e r v e r t m e s in P(x) and P(y)) E5. [Assign a vertex label.] Set v ~-~ M A T E ( y ) . If v m nonouter, set L A B E L ( v ) ~ x, F I R S T ( v ) ~- y, and go to E2 (See Figure 3 ) E6. [Get next edge.] Go to E2 (y is nonouter and M A T E ( y ) is outer, so edge xy adds nothing). E7. [Stop the s e a r c h ] Set LABEL(O) *-- --1. For all outer vertices % s e t L A B E L ( q ) L A B E L ( M A T E ( z ) ) ~-- --1 T h e n go to E1 (now all vertmes are nonouter for t h e n e x t search). e- L assigns the edge label n(xy) to nonouter vertices Edge xy joins outer vertices x, y. L s e t s join to t h e first nonouter vertex m both P ( z ) and P(y). T h e n it labels all n o n o u t e r vertices preceding join in P(x) or P(y) See Figure 4. L0. [Initialize.] Set r ~ F I R S T ( x ) , s ~-- F I R S T ( y ) . If r = s, r e t u r n (no vertices c a n be labeled). Label (v) ' P(v) Flrlt(v) Mate(y)q FIG. 3 v Assigning a vertex label 226 HAROLD N. GABOW loin - - - r P(v) s X Wy (a) (b) FIG. 4. Assigning edge labels Otherwise flag r and s. (Steps L1-L2 find 3oin by advancing alternately along paths P ( x ) and P(y). Flags are assigned to nonouter vertices r in these paths. This is done by setting L A B E L ( r ) to a negative edge number, L A B E L ( r ) +- - n ( x y ) . This way, each invocation of L uses a distinct flag value.) L1. [Switch paths ] If s ~ 0, interchange r and s, r ~-~ s (r is a flagged nonouter vertex, alternately in P ( x ) and P(y)). L2. [Next nonouter vertex.] Set r +-- F I R S T ( L A B E L ( M A T E ( r ) ) ) (r ]s set to the next nonouter vertex in P(x) or P(y)). If r is not flagged, flag r and go to L1 Otherwise s e t 3 o i n ~-- r and go to L3. L3. [Label vertices in P(x), P(y).] (All nonouter vertmes between x and 3o~n, or y and jozn, will be assigned edge labels. See Figure 4(a).) Set v +- F I R S T ( x ) and do L4. Then set v +- F I R S T ( y ) and do L4. Then go to L5. L4 [Label v ] If v ~ 3oin, set L A B E L ( v ) +- n(xy), F I R S T ( v ) ~-)oln, v ~-- F I R S T ( L A B E L ( M A T E ( v ) ) ) and repeat step L4 (See Figure 4(b).) Otherwise continue as specified in L3. L5 [Update F I R S T . ] For each outer vertex i, if F I R S T ( I ) is outer, set F I R S T ( z ) +- 3o~n. (Join is now the first nonouter vertex in P(i) ) L6. [Done ] Return R (v, w) rematches edges m the augmenting path. Vertex v is outer. Part of path (w)*P(v) is in the augmenting path. It gets rematehed by R(v, w) (Although R sets M A T E ( v ) +- w, it does not set M A T E ( w ) ~- v. This is done in step E3 or another call to R.) R is a recursive routine. R]. [Match v to w ] Set t ~-- M A T E ( v ) , M A T E ( v ) ~- w. If M A T E ( t ) ~ v, return (the path m completely rematehed) R2. [Rematch a path.] If v has a vertex label, set M A T E ( t ) ~-- L A B E L ( v ) , call R ( L A B E L ( v ) , t) recursivcly, and then return. R3. [Rematch two paths.] (Vertex v has an edge label ) Set x, y to vertices so L A B E L ( v ) = n ( x y ) , call R(x, y) recurslvely, call R ( y , x) recurslvely, and then return. W e illustrate h o w E c o n s t r u c t s a m a x i m u m m a t c h i n g on g r a p h Gi of F i g u r e 1. Initially, all v e r t i c e s are u n m a t c h e d . E searches for an a u g m e n t i n g p a t h t o v e l t e x 1. T h e first edge chosen, 12, f o r m s such a p a t h . A n a u g m e n t is d o n e b y placing 12 in t h e m a t c h i n g . E sets M A T E ( l ) ~-- 2, M A T E ( 2 ) +- 1. I n a similar m a n n e r , edges 34, 56, a n d 78 are m a t c h e d . T h i s gives t h e m a t c h i n g in F i g u r e 1. An Effwient Implementation of Edmonds' Algorithm 227 9 p(T)--- FxG. 5. i Search from vertex 9 ]n the last search, vertex 9 gets a start label. Edge 93 is scanned, and vertex 4 gets a vertex label; similarly, vertices 6 and 8 get vertex labels. When E scans edge 48, vertex 7 gets an edge label. The result is Figure 5. (Only scanned edges are shown. The L A B E L values of outer vertices are shown in Figure 2.) Now we describe how vertices 3 and 5 are labeled, as shown in Figure 2. E scans edge 67, and subroutine L is called to assign the label n(67). L computes join in steps L0-L2, as follows: 1. In step L0, the first nonoutcr vertex in P(6) is computed as F I R S T ( 6 ) = 5. The first nonouter vertex in P(7) is computed as F I R S T ( 7 ) = 3. Vertmes 5 and 3 are flagged by setting L A B E L ( 5 ) ~-- L A B E L ( 3 ) ~ - n ( 6 7 ) . 2. In step L2, the next nonouter vertex in P(7) is computed as F I R S T ( 9 ) = O. Vertex 0 is flagged. 3. In step L2, the next nonouter vertex in P(6) is computed as F I R S T ( 9 ) = O. Since 0 is already flagged, joan is set to 0. In steps L3-L4, L assigns the label n(67) to vertices 5 and 3. L resets F I R S T ( i ) for i = 4, 6, 7, 8, in step L5. No nonouter vertices remain in P(~), so F I R S T ( I ) is set to 0. Finally, L returns. Now E continues scanning edges. Vertex 2 gets a vertex label; the result is Figure 2. When edge 32 is scanned, vertex I gets an edge label, n(32). Finally edge 1 10 is scanned, and the augmenting path (10).P(1) is found. The augment is done in step E3 and subroutine R. Step E3 matches vertex 10, and calls R(1, 10) to rematch the remainder of (10),P(1). Figure 6(a) shows the result of R(1, 10): Edge 1 10 is matched, and two recursive calls are pending on R, R(3, 2) and R(2, 3). (In Figure 6(a), edge 12 is drawn half-wavy, denoting M A T E ( 2 ) -- 1 but M A T E ( l ) ~ 2.) Path P(1) is defined as (rev P(2, 1 ) ) . P ( 3 ) . The call R(3, 2) processes path P(3). Figure 6(b) shows the matching when R(3, 2) is complete. (R(3, 2) makes recursive calls R(6, 7) and R(7, 6).) Then the call R(2, 3) processes path rev P(2, 1). It sets M A T E ( 2 ) = 3, completing the augment. Now M A T E contains a maximum matching. The algorithm halts in step El. 228 HAROLD N. GABOW 9 I0 9 I0 I, ./i ) 5 ) I 3 S 4 6 rey~.P (a,I)- l Pll (o) (b) FIG. 6. Augment path (10).P(1) For comparison we briefly describe how Edmonds' algorithm [4] finds the" same matching on G~. We discuss the search for an augmenting path to vertex 9. The search begins by growing a tree consisting of the edges in Figure 5, except for edge 48. When this edge is scanned, it completes a cycle, (4, 7, 8, 4). Edmonds defines a blossom as an odd number of vertices joined by a maximally matched cycle. Vertices 4, 7, and 8 form a blossom. These vertices and the edges between them are shrunk into a single vertex, b. Vertex b is adjacent to any vetrex adjacent to 4, 7, or 8, b is matched with vertex 3. The result is a reduced graph Gt'. Now the problem is to find all augmenting path in G(. Suppose the path (10, 1, 2, 3, b, 6, 5, 9), corresponding to (10),P(1), is found. The matching in Gi' is augmented. So edge b6 becomes matched. Then blossom b is expanded into the original cycle (4, 7, 8, 4). Vertex 7 is matched to 6. The remaining vertices are matched along edges of the cycle. The result is a maximum matching. The intermediate steps that find the augmenting path in G~' are similar. Two more blossoms are shrunk. (These correspond to edge labels n(67) and n(32).) In the augment, these two blossoms are expanded and rematched. The implementation of this elegant algorithm requires some care. A time bound of O(V 4) results from (possibly) V2 blossom expansion operations, each requiring time 0(V2). Algorithm E avoids shrinking and expansion by recording the pertinent structure of blossoms in L A B E L and F I R S T . This results in a factor of V speedup. 4. Proof of Correctness This section proves that Algorithm E constructs a maximum matching. It shows that E constructs valid augmenting paths; each matching is augmented correctly; and the last matching is maximum. I t is convenient to introduce the dummy vertex, 0, to handle boundary conditions. In any search, we assume vertex 0 is nonouter, and is "matched" with the unmatched vertex u. We also extend the paths P(v) to vertex 0, as follows: Defimtion 1. An outer path is an alternating path (v, vl, . . . , u, 0) that starts with a matched edge vvl and ends with the dummy vertex, 0. The definition guarantees an outer path contains at least one nonouter vertex. An E~cient Implementation of Edmonds' Algorithm plv)----J~ plr*j-l,rjl ~ r'lj-I " 229 w FIG. 7. Search graph The first task is to prove that in step E3, ( y ) , P ( x ) is an augmenting path. I t suffices to show t h a t P(x) is an outer path. We do this below, in Corollary 1. The main issue is proving P(x) is simple. We start b y defining a search graph, which gives the properties of a search conducted b y E. Functions p, f, and l in the definition correspond to P, FIRST, and LABEL in Algorithm E. Defin~tw~ 2. A search qraph (G, O, u, p, f, l) consists of: a matched graph G; a set of vertices, O, called outer vertices; an unmatched outer vertex u; a function p, mapping an outer vertex v to p(v), an outer p a t h starting at v; a function f, mapping an outer vertex v to f(v), the first nonouter vertex in p(v); and a function l, mapping certain outer vertices v to l(v), another outer vertex. In addition, the following properties are satisfied for an outer vertex v. Let r = f(v), the first nonouter vertex in p(v); let r - be t h e vertex matched with r; and let r + = l(r-). 2.1. P a t h p(v) = p(v, r).p(r+). 2.2. An outer vertex x in p(v, r) h a s f ( x ) = r. Figure 7 shows an outer path p(v) in a search graph. All outer vertices x with the same vertex f(x) are grouped in a circle. Vertex r = f(v) is the first nonouter vertex in path p(v). Consider a vertex x in v's circle. Properties 2.1 and 2.2 imply t h a t p(x) consists of a path inside the circle to r - ; followed by edges r-r, rr+; followed by p(r+). ( N o t e t h a t the circles in Figure 7 correspond to blossoms in Edmonds' algorithm.) Figure 2 shows a search graph constructed by E. The outer vertex 3 illustrates property 2.2, since all vertices x in P ( 3 , 9) have F I R S T ( x ) = O. The decomposition property 2.1 at first seems too weak. I t seems natural t h a t p(v) = (v, vl, . . . , v2,-1, v2,, . . . ) decomposes as p(v, v2,-1)*p(v~,), for any i. However this is false. In Figure 2, p ( 3 ) ~ (3, 4 ) , p ( 8 ) . 230 HAaOLV ~ . GABOW Now we derive the structure of p a t h p(v) shown in Figure 7. Let the nonouter vertices in p(v) be r , , for 0 < j < J. Thus r0 ~- r = f(v) and r j = 0. Property 2.1 shows t h a t for a n y i i n 0 < i _ < J, p(v) = p(v, r0).p(r0 +, r l ) * - . " *p(r~+-l, r,)* . . . . p ( r , + ) . (1) A vertex x ~ re in p(r~-l, re) is outer, a n d f ( x ) = re. Next we derive the relationship between two outer paths p(v) and p(w), as shown in Figure 7. Let the nonouter vertices in p(w) be sk, for 0 _< k < K. Let z be the first outer vertex in p(v) t h a t is also in p(w). Decomposition (1) shows f(z) is a nonouter vertex in b o t h paths, f(z) = rs = sa for some indices f, g. So it is easy to see t h a t p(v) and p(w) are identical after rf = so, and t h a t p(v, rs_l ) and p(w, so-l) are disjoint. Thus, as shown in Figure 7, p(v) and p(w) both partition into three subpaths. The first subpaths, p(v, rf_~) and p(w, Sa-l), are disjoint; the last subpaths, p(rs +) and p(so+), are identical; the middle subpaths, p( r~-x , rs ) and p( so+-l , so), intersect arbitrarily. Now we show t h a t E maintains a search graph. First we formally define the function P : Definitwn 3. The outer path functwn P for Algorithm E is defined (recursively) as follows: 1. The unmatched vertex u has outer p a t h P(u) = (u, 0). 2. If v has a vertex label, LABEL(v) is the number of an outer vertex, and P(v) = (v, MATE(v) ),(LABEL(v) ). 3. If v has an edge label, LABEL(v) is the number of an edge xy, where x and y are outer vertices. Either v E P(x) or v E P(y). In the former case, P(v) = (rev P(x, v) ) . P ( y ) ; otherwise, P(v) = (rev P(y, v) ) . P ( x ) . LEMMA 1. Each time step E2 is executed m Algorithm E, a search graph is formed by (G, O, u, P, FIRST, LABEL). PROOF. The argument is b y induction. Assume a search graph is formed, with outer vertices O. Below we show t h a t if E assigns an edge label n(xy) to new vertices 0 I, then a search graph is formed, with outer vertices O U 0'. The case where E assigns a vertex label is left as an easy exercise. Edge labels are assigned in step E4 and subroutine L. F r o m Figure 7, we see steps LO--L4 work as follows: I n steps LO-L2, consecutive nonouter vertices in P(x) and P(y) are flagged. ( I n a search graph, the nonouter vertex after r is f(l(r-)). ) In step L2, join is set to the first nonouter vertex common to P(x) and P(y). (In Figure 7, 3oin = ry = so.) In step L4, a label is assigned to each nonouter vertex v preceding josh in P(x) or P(y). Now we check the search graph properties for an outer vertex v. We assume first v E O, and then v E O'. If v E O, let r be the vertex FIRST(v) before L is executed. We assume r is labeled in step L4, since otherwise there is nothing new to check. Either r E P(x) or r E P(y) ; assume the former. Figure 7, applied to paths P(v) and P ( x ) , shows t h a t these paths are identical after r. So after L is executed, the first nonouter vertex in P(v) is join. The value FIRST(v) is set to join in step L5. Thus array F I R S T is maintained correctly. Properties 2.1 and 2.2 follow easily from (1). Thus vertices in O satisfy all search graph properties. Now we check these properties for ~ vertex v E 0 ' . Before step L4, v is a nonouter vertex in P(x) or P(y). Assume the former, so P(v) = (rev P(x, v)),P(y). Thisdefines an outer p a t h (see Figure 7). I n particular, P(v) is simple, since P(x, v) and P(y) are disjoint. Thus P(v) is defined correctly. The remaining search graph properties for v follow from those for vertices x, y E O. The lemma now follows b y induction. [] COROLLARY 1. E labels vertices v so P ( v ) is an outer path starting at v. A n Effwient Implementation of Edmonds' Algorithm 231 Thus we see t h a t E constructs valid augmenting paths. Next we show t h a t E augments a matching correctly. We begin with two useful definitions. In an augment, step E3 and subroutine R change values of M A T E . A nonzero vertex v is originally matched if M A T E ( v ) is unchanged from its value before step E3 begins. F o r example, in Figure 6(a), all vertices except 1, 10, and 0 are originally matched. Define a partial order on vertices, @, as follows: v © w means t h a t v is an outer vertex, and v is labeled before w is labeled. In Figure 2, 9 © 7 © 1. We consider vertices labeled in the same call to L as being labeled simultaneously. So neither 3 © 5 nor 5 @ 3. LEMMA 2. Let R(v, w) be called, with v an outer vertex and w ~ P ( v ) . Suppose the first vertex of P ( v ) = (v, vl , v~ , • • • ) that is not originally matched is v2m+l , and v ~ v~m+l. Then R changes M A T E ( v , ) , 0 < i < 2m, to give a maximum matching of the path ( w ) . P ( v , v2m)(i.e. M A T E ( v ) = w, and for 1 < ~ _< m, MATE(v2,-1) = v2,, M A T E ( v ~ , ) = v2,-1). PROOF. The proof is b y induction on m. The argument falls into three cases: m = 0 ; m > 0 a n d v h a s a v e r t e x l a b e l ; m > 0 a n d v h a s a n edgelabel. F o r details, see [8]. [] COROLLARY 2. E augments a matching correctly. PROOF. We show t h a t after step E3 and R are executed, M A T E is changed according to an augment along the p a t h ( y ) . P ( x ) . The value M A T E ( y ) is set correctly in step R3. When R ( x , y) is called, all vertices in P ( x ) are originally matched, except vertex 0. The hypotheses of the lemma are satisfied with v~m+l = 0. So when R ( x , y) returns, M A T E is changed to give a maximum matching of ( y ) . P ( x ) . [] The final task is to show the last matching is maximum. Suppose vertex u is unmatched in the last matching. I n some execution of step E l , a search is started from vertex u. This search terminates without augmenting. Let S~ denote the search; let M~ denote the matching when search S~ is made. We investigate how subsequent searches interact with S,,. The following concept is central [4]. Definition 4. The Hungarian subgraph H for vertex u is a subgraph of G. I t consists of all edges containing an outer vertex of S~, and all vertices in these edges. In G1, if edge 23 is deleted, Figure 2 shows the Hungarian subgraph for vertex 9. Note these obvious properties of a Hungarian subgraph H : In search S~, each edge of H is chosen at least once in step E2. If vertex v E H - u, the matched edge containing v is in H. The basic result is t h a t no augmenting path constructed after S , intersects H. LEMMA 3. Suppose a matching M agrees with M~ on H, M N H -- M , N H. Then no augmenting path for M contains a vertex zn H. PROOF. The hypothesis implies we can refer to "a matched edge in H " unambiguously. We do so below. Let Q be an augmenting path for M containing a vertex in H. We derive a contradiction, proving the lemma. P a t h Q is not contained entirely in H. So we can set Q = (vl, v2, • • • , v2,), where for some i in 1 _< i < n, vertex v2,+~ E H and v~+2 ~ H. The matched edge v2,v~,+l is in H. So a vertex in this edge is outer in S , . Since v2,+~is nonouter, v2, is outer. Choose an index j, 0 < j < i, so p a t h Q' = (v2j, v2j+l, -. • , v2,+1) is in H, and vertex v~ is outer for j < k < i b u t nonouter for j = k. This can be done, since if v2k is outer in H, then the matched edge v:k-2v2k-~is in H. (Note i f j = 0, we have vo = 0 and vl = u.) We derive a contradiction b y calculating FIRST(v2~+i) at the end of S~. If x and y are adjacent outer vertices, then at the end of S , , F I R S T ( x ) = F I R S T ( y ) . (This results from executing subroutine L on edge xy.) Applying this observation to vertices in p a t h Q' shows FIRST(v2~+i) -- v2~+1, the first nonouter vertex in Q'. (This vertex exists, since v2~+~ is nonouter.) However, p a t h P(v~+~) = (v2~+1, v 2 ~ , . . . ), so FIRST(v2j+i) = v2j. Since v2~ v2~+~, we have a contradiction. [] Now we show E works correctly. 232 HAROLD N. GABOW TABLE I. Wons~-C~,sE TI~E BouNns Steps Time Executions per search Total time EO El E2 E3-R E4-LO V + W c c V c -V 2W 1 W Vs V V* V2 V* LI~L6 V V/2 V* E5 E6 E7 c c V V /2 W 1 V* Vl V~ COROLLARY 3. E halts wzth a maximum matching specified by M A T E . PltooF. F i m t note t h a t E always halts. We have seen t h a t subroutines L and R halt. So any search eventually stops, in step E2 or E3. E starts a finite number of searches in step E l . So Algorithm E halts. Corollary 2 shows t h a t M A T E specifies a valid matching when E halts. To prove the last matching is maximum, it suffices to show no augmenting p a t h exists, b y Berge's Lemma. Let u be an unmatched vertex. Lemma 3 shows no augment made b y E after S~, involves edges in H. So Lemma 3 can be applied to the last matching, to show there is no augmenting path to u. [] We conclude this section b y describing a useful modification to Algorithm E, due to Edmonds [4]. The idea is to ignore a Hungarian subgraph H in searches after S~. ( B y Lemma 3, searching in H is fruitless. ) We change step E2 as follows: E2'. [Choose an edge.] Choose an edge . . . If no such edge exists, go to El. Step E2 pcauses step E7, which unlabels vertices, to be skipped after S~. I t is easy to check t h a t in the modified algorithm, a vertex y E H is never labeled in a search after S~. This modification speeds up the algorithm if a maximum matching contains unmatched vertices. I t does not change the worst-case time bound. 5. E~cieney and Applications Algorithm E requires at most O(V ~) time units when executed on a random access computer. This is seen from Table I, which gives simple bounds on the time for each step. F o r example, steps E4-LO can be executed in a constant amount of time (c) ; in a given search, they are executed at most W times (where W is the number of edges) ; since there are at most V searches, and W g V( V - 1)/2, the total time for these two steps is O(V~). (Note t h a t in step E2 we assume edges are chosen in a breadth-first or similar method, where a list of outer vertices is maintained. The list allows an unexamined edge to be chosen in time c J) Families of graphs t h a t require time O(V 3) can be constructed. We describe such a family, assuming Algorithm E uses the breadth-first method in step E2. Similar families can be constructed for other methods [8]. Figure 8 ( a ) shows a graph G6~, with a maximum matching. This graph is formed from vertices 1, 2, .. • , 6m b y joining vertices 1, 2, • .. , 4m in a complete graph, K4~, and joining vertex 2i -- 1 with vertex 4m "-b i, for 1 < i < 2m. Adjacency lists contain vertices in numerical order. Figure 8(b) shows the intermediate matching with 2m edges constructed b y Algorithm E. Figure 8(c) illustrates a typical search to match vertex 4m -b i. ( H e r e / i s odd.) All vertices except 1, 3, 5, • • • , 2/ - 1 are made outer. An augmenting 1 The run time of Algorithm E is at most O(VWa(W, V)), if an efficient set merging algorithm is used to maintain FIRST in step L5. Here a is a very slowly growing function; a(W, V) < 3 for all graphs that can be stored in an existing computer memory [12]. For sparse graphs (W << V~), this variant of E is preferable. An Effwient Implementation of Edmonds' Algorithm 4m,l 4m*i 2i.ll (b) 4m.Sitl 2i , 4m4i 233 6m 2it,! 2it2 K4m 4m,itl (o) K4m 4m~i ir (c) I~ 4m,I 4 4 m 4m,2 - I 4m,i-I 2it2 4m FIG. 8. Worst-case graph G~ path to vertex 4m "4- i + 1 is found when outer vertex 2~ + 1 is chosen in step E2. Over 4mi edges are chosen in this search, and over 4m 3 edges are scanned in the last m searches. Thus the time is O(V3). Several experiments were conducted with an implementation of E in Algol W on the I B M 360/165. For the worst-case graphs described above, run times proportional to V 2"s were observed, over the interval 11 _< m < 24 (66 < V < 144, 968 < W < 4608), with times from .18 to 1.6 sec. For a similar experiment on Edmonds' algorithm, times proportional to V ~ 5 were observed (versus V 4 predicted) with time 1.7 sec for m = 11. Experiments on E on "random" graphs gave times one order of magnitude faster than worst-case graphs with 3200 edges [8]. The space used by the Algol W implementation of E is 5V + 4W words. This includes V -4- 4W words for the graph; 2V words for MATE and LABEL; V words for FIRST, also used by the stack of recursive calls to R; and V words for a list of outer vertices for step E2. Algorithm E can be used to speed up the scheduler devised by Fujii et. al. [6]. They solved the following problem: Compute an optimal schedule for N tasks to be executed by two processors, assuming the tasks have equal length and arbitrary precedence constraints. Their approach is to construct a compatibility graph, showing which tasks can be executed simultaneously; then find a maximum matching on the compatibility graph; finally, sequence the matched task pairs and the unmatched tasks according to precedence con- 234 HAROLD N. GABOW straints. This algorithm was thought to require time 0(N4)[6, Erratum]. But thefirst and last steps can be executed in time O(Na), and Algorithm E finds the matching in time O(N:~). So the scheduler is an O(N 3) algorithm. (Recent work by Coffman and Graham [3] solves this scheduling problem in time O(N~). Their elegant method does not employ matchings directly.) Algorithm E can be generalized to find maximum matchings on weighted graphs. In a weighted graph, each edge has a weight that is a real number. The problem is to find a matching with maximum weight. Matching on ordinary graphs is the special case of this problem where all edges have equal weight. Edmonds [5] first developed an efficient (O(V4)) algorithm for this problem. The generalization of Algorithm E takes time 0(V3)[8]. ACKNOWLEDGMENTS. The author wishes to thank Professor Harold Stone of Stanford University for assisting in the preparation of this manuscript, and Professor Eugene Lawler of the University of California at Berkeley for communicating his stimulating ideas on matching. REFERENCES (Note. Reference [7] is not cited in the text.) 1. BALINSKI,M.L. Labelling to obtain a maximum matching In Comb~natomal Mathematics and Its Applications, R.C. Bose and T.A Dowling, Eds , U. of North Carolina Press, Chapel Hill, . 2 3 4 5. 6. 7 8. 9 10 11. 12 13. N.C., 1967, pp. 585--602 BERGE,C. Two theorems in graph theory. Proe. Nat. Acad. Sc~. $S (1957), 842-844. COFFMAN,E J. JR., AND GRAHAM, R L Optimal scheduling for two-processor systems. Acta Informatica 1 (1972), 2(}0-213. EDMONDS,J. Paths, trees and flowers. Canad J. Math. 17 (1965), 449-467 EDMONDS,J Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur Standards 69B (1965), 125-130 FuJII, m., KASAMI, T., A N D NINOMIYA,K. Optimal sequencing of two eqmvalent processors. S I A M J. Applied Math. 17 (1969), 784-789; Erratum, 20 (1971), 141. GAnow, H. An efficient ]mp|ementation of Edmonds' maximum matching algorithm Tech. Rep. 328, Comput. Sci. D e p , Stanford U., Stanford, C a h f , 1972 GABow, H. Implementations of algorithms for maximum matching on nonbipartite graphs. Ph.D. diss., Comput. Sci. Dep., Stanford U., Stanford, Cald., 1973. HARARY,F. Graph Theory. Addison-Wesley, Reading, Mass., 1969. I~NUTH,D The Art of Computer Programming, Vol. 1. Addison-Wesley, Reading Mass, 1968. TARJAN,R.E. An efficient planarity algorithm. Tech. Rep. 244, Comput. Sci. Dep., Stanford U., Stanford, Calif., 1971. TAaJAN, R.E. Efficiency of a good but not linear set union algorithm. J. ACM $2, 2 (April 1975), 215-225. WITZGALL,D., AND ZXHN, C T. JR. Modification of Edmonds' algorithm for maximum matching of graphs. J. Res. Nat. Bur. Standards 69B (1965), 91-98. RECEIVEDAPRIL1973; REVISEDJULY1975 Jounaa[ of the AMoclatlon for Computilag Machinery, rot. 2,~, No. 2. April 1976

© Copyright 2018