The Weighted Matching Approach
to Maximum Cardinality Matching
Harold N. Gabow∗

arXiv:1703.03998v1 [] 11 Mar 2017

March 10, 2017

Abstract
√
Several papers have achieved time O( nm) for cardinality matching, starting from first
principles. This results in a long derivation. We simplify the task by employing well-known
concepts for maximum weight matching. We use Edmonds’ algorithm to derive the structure of
shortest augmenting √
paths. We extend this to a complete algorithm for maximum cardinality
matching in time O( nm).

1

Introduction

The most efficient known algorithms for cardinality matching on nondense graphs achieve time
√
O( nm). The best known of these algorithms are not readily accessible: Micali and Vazirani were
first to present such an algorithm [9] but proving it correct has met difficulties [12, 13]. Gabow
and Tarjan present a complete development but only at the end of a long paper with a different
goal, a scaling algorithm for weighted matching [4]. Similarly Goldberg and Karzanov develop
a new framework for flow and matching problems (“skew symmetric matchings”) and again the
cardinality matching algorithm requires mastery of this framework. Each of these papers tackles a
difficult subject from first principles.
√
This paper presents an accessible matching algorithm with time bound O( nm). We simplify
the task by taking advantage of the well-established theory for maximum weight matching. We
include a review of Edmonds’ weighted matching algorithm [2] but still it is helpful to be familiar
with the algorithm. Complete treatments are in various texts e.g., [1, 8, 10, 11].
At first glance maximum weight matching seems to offer little insight to the problem. However
the dual variables for weighted matching reveal structure that can either be used directly or must
be rederived in a presentation from first principles. More importantly we show that a judicious
choice of edge weights maps a large piece of the puzzle into simple properties of weighted matching.
The use of weighted matching for cardinality matching was introduced by Gabow and Tarjan
[4]. Their cardinality matching algorithm uses a relaxation of the linear program duals that is
helpful for scaling. Our algorithm is based on the LP duals. In that respect it differs from [4] at
the structural level.
However to make our presentation complete, at the data structure level we use the depth-first
search procedure of [4], especially because of its simplicity. We also give a more detailed analysis of
the procedure’s correctness than [4], in an appendix. An alternative for this part of the algorithm
∗

Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado 80309-0430, USA. Email: hal@cs.colorado.edu

1

is the double depth-first search algorithm of Micali-Vazirani [9]. We use Edmonds’ algorithm to
deduce the key structure for this algorithm, in another appendix.
The paper presents our algorithm in a top-down fashion. Section 2 gives the overall approach,
using two Phases. Section 3 uses Edmonds’ algorithm to implement Phase 1. Section 4 restates
the Gabow-Tarjan algorithm for Phase 2 [4], with a complete correctness proof in Appendix A.
Section 5 gives details of the data structure that achieve our desired time bound. Appendix B uses
Edmonds’ algorithm to prove existence of the starting edge for the double depth-first search of the
Micali-Vazirani algorithm [9].
Terminology The given graph is always denoted as G = (V, E). An edge in a minor of G is
denoted as its preimage, i.e., xy for x, y ∈ V . For a set of vertices S ⊆ V , γ(S) denotes the set of
edges with both ends in S.
A matching M on a graph is a set of vertex-disjoint edges. M has maximum cardinality if it
has the greatest possible number
P of edges. Let each edge e have a real-valued weight w(e). For a
set of edges S define w(S) = e∈S w(e). M has maximum weight if w(M ) is maximum.
For an edge xy ∈ M we say x and y are mates. A vertex is free if it is not on any matched edge.
An alternating path is a vertex-simple path whose edges are alternately matched and unmatched.
(Paths of 0 or 1 edges are considered alternating.) An augmenting path P is an alternating path
joining two distinct free vertices. To augment the matching along P means to enlarge the matching
M to M ⊕ P (the symmetric difference of M and P ). This gives a matching with one more edge.

2

The approach

A shortest augmenting path, or sap, is an augmenting path of shortest length possible. Hopcroft
and Karp [6] and independently Karzanov [7] presented an efficient approach to finding a maximum
cardinality matching: Repeatedly find a maximal collection of vertex-disjoint saps and augment
√
the matching with them. This algorithm repeats only O( n) times [6, 7]. Fig.1 gives our implementation of this approach.
M ←∅
loop
/* Phase 1 */
for every edge e do w(e) ← if e ∈ M then 2 else 0
execute a search of Edmonds’ weighted matching algorithm
if no augmenting path is found then halt /* M has maximum cardinality */
form the graph H of permissible edges
/* Phase 2 */
P ← a maximal set of vertex-disjoint augmenting paths in H
augment M by the paths of P
Figure 1: The high-level cardinality matching algorithm.
We will show that Edmonds’ algorithm halts having found an sap (unless there is no augmenting
path). Furthermore it provides the information needed to construct the graph H, which has the
property that the saps of G correspond 1-to-1 to the augmenting paths in H. We will complete the

2

make every free vertex the (outer) root of an S-tree
/* general algorithm also makes free blossoms into roots */
loop
if ∃ tight edge e = xy with x outer, Bx 6= By then
if y ∈
/ V (S) then /* grow step */
add xy, yy 0 to S, where yy 0 ∈ M
/* general algorithm adds blossom By & its matched blossom */
else if y is outer then
if x and y are in the same search tree then /* blossom step */
merge all blossoms in the fundamental cycle of e in S
else /* xy plus the S-paths to x and y form an augmenting path */
return /* general algorithm proceeds to augment the matching */
/* general algorithm may expand an inner blossom */
else /* dual adjustment step */
δ = min{y(e) − w(e) : e = uv with u outer, v ∈
/ V (S)} ∪
{(y(e) − w(e))/2 : e = uv with u, v in distinct outer blossoms}
/* general algorithm includes set for duals of inner blossoms */
if δ = ∞ then return /* M has maximum cardinality */
for every vertex v ∈ V (S) do
if v is inner then y(v) ← y(v) + δ else y(v) ← y(v) − δ
/* general algorithm changes duals of blossoms. in particular
z(B) ← z(B) + 2δ for every maximal outer blossom B. */
Figure 2: Simplified search of Edmonds’ algorithm.

algorithm using one of several known algorithms to find the maximal set of augmenting paths P.
√
Every iteration will use O(m) time so the entire algorithm uses O( nm) time.

3

Phase 1 via Edmonds’ algorithm

Section 3.1 states the simplified version of Edmonds’ algorithm that we use. It also gives a brief
review of blossoms. Section 3.2 characterizes the augmenting paths that are found. Section 3.3
gives the algorithm for Phase 1 and proves the graph H has the key property.

3.1

Edmonds’ weighted matching algorithm

Fig.2 gives pseudocode for a search of Edmonds’ weighted matching algorithm [2]. The figure omits
code that is never executed in the special case of Edmonds’ algorithm that we use. Omissions are
indicated by comments. (Basically they result from the fact that there are no blossoms at the
start of a search.) We will explain the code of the figure and then give a precise statement of the
assumptions that simplify the code (see (A) below). In the figure M denotes the matching, Bx is
the blossom containing vertex x, see below.
The algorithm is illustrated in Fig.3. Free vertices are square and matched edges are heavy.
The dashed edges of Fig.3(f) form an augmenting path. The numbers in Fig.3 are defined below.
The algorithm builds a “search structure” S, a subgraph of G. (Fig.3(b)–(e) show the various
S structures.) It also maintains S, the subgraph S with various sets (called “blossoms”, defined
3

−1

−1

−3

1

1

1

3

3

3

1

1

1

−1

−1

−1

1

(a)

4

1

1

1

1

1

1

(c)

−5

−5

4

4

1

(b)

−4

−4

−3

5

−6

4v

4

5

5

−6

f

6
2

−2

−2

−2

−3

−4

4

2
0

−3

−3

0

2

2

2

0

0

−4

4

−1
−1

0

−4

2

1

1

3

−2
−2

−1 −1

−1

0

0

4

−2

−2

2

−2

2
1
(d)

(e)

1

0

0

(f)

Figure 3: (a) Example graph for finding an sap. Unmatched edges weigh 0, matched edges weigh
2. (b)–(f) Search of Edmonds’ algorithm. (b)–(e) show S, with inner vertices drawn hollow, and
the y and z dual variables. (f) shows the augmenting path as dashed edges.
below) contracted. S is a forest. Its roots are the free vertices and contracted sets that each
contain a free vertex. S is an “alternating forest” [2]: Any path from a node to the root of its
tree is alternating. A node of S is inner (respectively outer) if its path starts with an unmatched
(matched) edge. An inner node is always a vertex of G. An outer node can be a contracted set.
Any vertex of V in such a set is also called outer.
The algorithm adds new vertices and edges to S in a grow step, which adds an edge from an
outer vertex to a new inner vertex y. It also adds the matched edge from y to its mate, a new outer
vertex. (Fig.3(b) shows the result of three grow steps.)
Suppose the algorithm discovers an edge e joining two outer vertices. If e joins two distinct
trees of S it completes an augmenting path. An augment step enlarges the matching. (Fig.3(f)
shows the algorithm’s augmenting path as dashed edges.)
If e joins nodes in the same tree of S a blossom step is done: e is added to S, and the fundamental
cycle C of e in forest S is contracted. The vertices of V belonging to contracted nodes on C form
a blossom. (A blossom step is executed in each of Fig.3(c), (d), and (e).)
To describe the last step, recall that the algorithm is based on Edmonds’ formulation of weighted
matching as a linear program [2]. Each vertex v ∈ V has a dual value y(v). Each blossom B ⊆ V

4

has a nonnegative dual value z(B). The duals dominate an edge uv ∈ E if
X
y(u) + y(v) +
z(B) ≥ w(e).
v,w∈B

uv is tight if equality holds in this constraint. The algorithm maintains duals so that when z values
are included, every edge is always dominated. Furthermore every matched edge is tight, and an
edge triggering a grow, blossom or augment step must be tight. We use the common convention
that for e = uv ∈ E, y(e) denotes y(u) + y(v). Note that the test for tightness in Fig.2 has Bx 6= By
and so does not require z values.
When no grow, blossom, or augment step can be done, the algorithm makes progress by executing a dual adjustment step. It modifies dual variables so one or more of the other steps can be
performed. If this cannot be done the current matching has maximum cardinality. The modification
maintains the invariant that every edge of S is tight.
In Fig.3 each matched (respectively unmatched) edge weighs 2 (0). Each vertex is labelled with
its y-value. Each blossom is labelled with its z-value, even though these values are not recorded in
our algorithm. The label is in the interior of the blossom, and only included when z is nonzero. For
example the dual adjustment at the end of Fig.3(c) increases the z-value of the triangular blossom
from 0 to 2. This dual increases to 4 after part (d), and does not change in the dual adjustment
after part (e).
We conclude this section by stating the assumptions that allow our simplifications to the general
weighted matching algorithm:

(A)

• The algorithm begins with a matching M and no blossoms.
• The algorithm begins with dual variables y(v), v ∈ V that dominate every edge and
are tight on every matched edge (there are no z variables).
• The algorithm does not need to track z values of blossoms (since there will be no
subsequent search).

Blossoms It is convenient to consider every vertex as a blossom. But these singleton vertices do
not have a z dual. The notation Bx for x ∈ V denotes the maximal blossom containing x.
Any blossom B has a base vertex: The base vertex of a singleton B = {v} is v. The base vertex
of a blossom constructed in the blossom step of Fig.2 is defined as follows: The fundamental cycle
of e = xy in S contains a unique node of minimum depth – the nearest common ancestor a of x
and y. The base vertex of the new blossom is the base vertex of a. (In Fig.3(b)–(f) the base of any
blossom is the vertex closest to the root. For instance in part (e) the left subgraph is a blossom
whose base vertex is the root.)
Note that the base vertex of an arbitrary blossom B is the unique vertex of B that is not
matched to another vertex of B. It may be free or matched to a vertex not in B.
Any blossom B has a natural representation as an ordered tree RB . The root is a node corresponding to B. The leaves correspond to the vertices of V in B. Any interior node corresponds to
a blossom B 0 formed in the blossom step of Fig.2. Let the fundamental cycle C of that step consist
of blossoms Ci , i = 0, . . . , k. Here C0 contains the base vertex of B 0 , and the indexing corresponds
to the order of the blossoms in a traversal of C (in either direction). The children of B 0 correspond
to Ci , i = 0, . . . , k, in that order. In addition RB records the edge ci ci+1 that joins each child Ci to
the next child Ci+1 (taking k + 1 to be 0). These edges are alternately unmatched and matched.
Each matched edge has one of its ends a vertex of V (i.e., Ci = ci ). Each end is the base vertex of

5

its blossom. The base vertex of B is also recorded in RB , since it is not determined by a matched
edge of C.
Note that the edges ci ci+1 of RB all belong to E(S) and are tight. Also RB has O(|B|) nodes.
This follows since each B 0 has k + 1 children and k/2 matched edges. So the k + 1 children can be
associated with 2 · k/2 = k vertices of V in B (k ≥ 2).
Any vertex v ∈ B has an even-length alternating path P (v, b) ⊆ E(S) that starts with the
matched edge at v and ends at the base b. (The exception is P (b, b), which has no edges.) P (v, b)
is specified recursively using RB , as follows. Let Ci , i = 0, . . . , k be the children of the root B.
Let v belong to child Cj . The path P (v, b) passes through Ch for h = j, j + 1, . . . , k, 0 if cj cj+1 is
matched, else h = j, j − 1, . . . , 1, 0 if cj−1 cj is matched. Applying this description recursively to
the children Ch gives the entire path P (v, b). (Note that P (v, b) traverses some recursive subpaths
P (v 0 , b0 ) in reverse order, from b0 to v 0 . But the algorithm does not require this order.)
As an example, the augmenting path of Fig.3(f) traverses the blossom of Fig.3(e) on the path
P (v, f ) of length 10.
The paths P (v, b) are used (in the complete version of Edmonds’ algorithm, as well as our
algorithm in Phase 2) to augment the matching. Note that the order of edges in P (v, b) is irrelevant
for this operation, since we are simply changing matched edges to unmatched and vice versa. Also
note that every edge of P (v, b) is tight, since P (v, b) ⊆ E(S). So augmenting keeps every matched
edge tight.

3.2

Properties of Edmonds’ algorithm

Implicit in Edmonds’ algorithm is that it finds a maximum weight augmenting path. This section
proves this and characterizes the structure of all maximum weight augmenting paths. We make
this assumption on the initialization:
(A0 ) The initial y function is constant, with no unmatched edge tight.
A constant y is the usual initialization of Edmonds’ algorithm. Having no unmatched tight means
there is at least one dual adjustment – this assumption simplifies the notation.
As usual define the weight of a path P to be
w(P ) = w(P − M ) − w(P ∩ M ).
Lemma 3.1 At any point in Edmonds’ algorithm, any augmenting path P and any free vertex f
have w(P ) ≤ 2y(f ).
Proof: An edge rs is dominated if it is unmatched, i.e.,
X
(3.1)
w(rs) ≤ y(r) + y(s) +

z(B),

r,s∈V (B)

and equality holds if rs is matched. So replacing every term w(rs) in the definition of w(P ) by the
right-hand side of (3.1) gives an upper bound on w(P ). Any interior vertex of P , say r, has y(r)
appearing in both w(P − M ) and w(P ∩ M ). Hence the y terms in the upper bound sum to 2y(f ).
So it suffices to show the z terms have nonpositive sum.
Let B be any blossom and let b be its base. Every vertex of B except b has its mate contained
in B. P is not contained in γ(B) since P contains two free vertices. Consider a maximal length
subpath S of P ∩ γ(B). S is alternating. There are two cases:
6

Case S has b at one end: Following edges starting from b shows S ends at a matched edge of γ(B).
So S has even length, and its edges make no net contribution of z(B) terms to the upper bound.
Case Neither end of S is b: The first and last edges of S are matched. Thus S makes a net
contribution of −z(B) ≤ 0 to the upper bound.
We conclude the total contribution of z terms to the upper bound is ≤ 0, as desired.
2
Call a blossom B positive if z(B) > 0. B is positive iff it was formed before the last dual
adjustment.
The following corollary refers to the end of Edmonds’ search – tightness refers to the final duals,
and blossoms are as defined over the entire algorithm.
Corollary 3.2 An augmenting path P has maximum weight iff all its edges are tight and for every
positive blossom B, P ∩ γ(B) is an even-length alternating path.
Proof: The if direction follows from the proof of the lemma. Specifically the proof implies that
P achieves the upper bound of the lemma, i.e., w(P ) = 2y(f ), if every edge of P is tight and P
traverses positive blossoms as specified in the lemma.
In particular the augmenting path A found in the search algorithm satisfies these sufficient
conditions. (In fact A traverses every blossom as in the lemma.) Thus A is a maximum weight
augmenting path.
This implies an augmenting path has maximum weight iff its weight is 2y(f ). So the proof of
the lemma implies the conditions of the corollary must hold for the final dual variables and the
positive blossoms of the algorithm.
2

3.3

Phase 1

As in Fig.1 an edge weighs 2 if it is matched, else 0. We initialize Edmonds’ algorithm by setting
every y value to 1. This makes every matched edge tight, every unmatched edge dominated but not
tight, and y constant. Furthermore in every iteration of Fig.1 Edmonds’ algorithm starts afresh
with no blossoms. So the assumptions of (A) and (A0 ) hold.
Assuming the matching is not maximum cardinality, Edmonds’ algorithm halts with a maximum
weight augmenting path. Any augmenting path P of length |P | has
(3.2)

|P | = −w(P ) + 1.

So an augmenting path has maximum weight iff it is an sap.
The last step of Phase 1 constructs H, the graph whose augmenting paths correspond to the
saps of G. H is formed from G by contracting every positive blossom, and keeping only the tight
edges that join distinct vertices.1 As usual each edge of H records its preimage in E, allowing an
augmenting path in H to be converted to its preimage in G.
Phase 1 requires that the augmenting paths in H are precisely the images of the saps of G. We
will show this using Corollary 3.2.
Case P is an sap in G: Consider any positive blossom B with P ∩ γ(B) 6= ∅. The corollary implies
P ∩ γ(B) is a path that starts with a matched edge and ends with an unmatched edge incident to
the base vertex b of B. So P either contains exactly 1 edge incident to B (if b is free), or 2 edges
1

Edmonds’ search may end before exploring some tight edges. This does not affect the definition of H.

7

procedure find ap set
initialize S to an empty graph and P to an empty set
for each vertex v ∈ V do b(v) ← v /* b(v) maintains the base vertex of Bv */
for each free vertex f do
if f ∈
/ V (P) then
add f to S as the root of a new search tree
find ap(f )

1

2

3

4

5

procedure find ap(x) /* x is an outer vertex */
for each edge xy ∈
/ M do /* scan xy from x */
if y ∈
/ V (S) then
if y is free then /* y completes an augmenting path */
add xy to S and add path yP (x) to P
terminate every currently executing recursive call to find ap
else /* grow step */
add xy, yy 0 to S, where yy 0 ∈ M
find ap(y 0 )
else if b(y) is an outer proper descendant of b(x) in S − then /* blossom step */
/* equivalent test: b(y) became outer strictly after b(x) */
let ui , i = 1, . . . , k be the inner vertices in P (y, b(x)), ordered so ui precedes ui−1
for i ← 1 to k do
for every vertex v with b(v) ∈ {ui , u0i }, where ui u0i ∈ M do b(v) ← b(x)
/* this executes the blossom step for xy. each ui is now outer. */
for i ← 1 to k do find ap(ui )
return
Figure 4: Path-preserving depth-first search.

incident to B, one being the matched edge incident to b. In both cases the image of P in H is an
alternating path. This makes P an augmenting path in H.
Case P is augmenting in H: Consider any blossom node B on P . P contains an unmatched edge
incident to some vertex v ∈ B. Letting b be the base vertex of B, either b is free or P contains the
matched edge incident to b. In both cases we can add the P (v, b) path through B. Doing this for
every B on P yields a path in G, with all edges tight. The corollary shows P is an sap.

4

Phase 2

We can find a maximal set of augmenting paths in H using the double depth-first search of Micali
and Vazirani [9], or the algorithm of Goldberg and Karzanov [5], or the depth-first search of Gabow
and Tarjan [4]. To make this paper complete Fig.4 restates the algorithm of [4]. The find ap
algorithm is illustrated in Fig.5. This section discusses the idea of the algorithm and gives the
high-level analysis, for both correctness and the linear time bound O(m). Appendix A completes
the analysis. The development is similar to [4] but includes more details.
Note that the search of Micali-Vazirani [9] requires an additional property of H, which is proved
in Appendix B.

8

1

1

10

11

10

2

3

2

1

11

10

3,7,4,8,5

1,10,2

11

2

[1..11]

11

[3..9]

[3..9]

7
9
4
6
8

9

5

6

(a)

(b)

(c)

(d)

(e)

Figure 5: (a) Example graph for find ap. Vertices are numbered in the order they become outer.
(b)–(e) S after each of the four blossom steps of find ap. Dashed edges are not in S. [i..j] denotes
the set of consecutive integers {i, . . . , j}.
We first introduce a variant of previous notation that is used in the rest of the paper: S −
denotes the subgraph of S consisting of the edges added in grow steps. Clearly S − consists of trees
that span S. Also S is a contraction of S − . We use S − to state ancestry relationships (e.g., line 3 of
Fig.4). These relations essentially hold in S but S − has the advantage of being more stable. Note
that S − is not alternating. (For instance in Fig.5(a) add a matched edge aa0 with an unmatched
edge from 11 to a.)
Next we review Fig. 4. find ap implements a search of Edmonds’ cardinality matching algorithm
(the algorithm of Fig.2 with no dual variables, every edge is tight). In line 2 P (x) is the naturally
defined alternating path in H from x to f . Specifically P (x) is formed from the S-path from Bx to
Bf , by traversing every blossom of find ap using the appropriate P (v, b) path. In line 4 P (y, b(x))
can be traversed by simply using the S-path from By to Bx . Note this simple property of the base
vertex function b: b(v) is always an S − -ancestor of v.
The idea for find ap is to search for an augmenting path depth-first, making sure that all
vertices currently being explored remain on the current search path. This is an obvious property of
ordinary depth-first search. It is also desirable for finding disjoint augmenting paths: When we find
an augmenting path and delete it from further consideration, no problems are created by partially
explored vertices remaining in the graph – these vertices all get deleted.
To achieve this property blossom steps must be scheduled carefully. Fig.4 does this by delaying
blossom steps. (In Fig.5 mate(2) is the 10th vertex to become outer, not the third.) Also the
blossom step explores the new outer vertices ui in order of decreasing P (ui ) length. (Vertex 7 is
explored before vertex 8.)
It is easy to see that find ap correctly implements the grow and blossom steps of Edmonds’
cardinality matching algorithm. Specifically S, S, b(x), and P (x) correspond to their definitions.
However it is not immediately clear that find ap does every possible blossom step. This is proved
in Appendix A (Lemma A.4).
We close this section with a simple proof that find ap set is correct, assuming Lemma A.4.
Correctness means that find ap set halts with P a maximal set of vertex-disjoint augmenting paths.

9

The above remarks imply that each path of P is augmenting. So the issue is to prove maximality
– no augmenting path of H is vertex-disjoint from P.
At any point in the execution of find ap set call an outer vertex x completely scanned if find ap(x)
has returned in line 5. The other possibility for an outer x – x is not completely scanned – holds
when either find ap(x) has not been called, or it is currently executing, or it was terminated because
an augmenting path was discovered.
The important invariant is
(I)

Whenever line 1 of find ap(x) scans an edge, P (x) contains every outer vertex that has
not been completely scanned.

For instance when vertex 8 scans edge 8,6, vertex 7 is not in P (8) but it has been completely
scanned. It is easy to see invariant (I) is preserved when a recursive call is made: In the grow
step P (y 0 ) contains P (x); in the blossom step P (ui ) contains P (uj ), i < j ≤ k, and also P (x). So
(I) holds on entry to find ap(x). Any vertex that becomes outer after this is completely scanned
whenever control returns to find ap(x). So (I) holds throughout the execution of find ap(x), and
throughout the entire algorithm.
(I) implies that any augmenting path added to P contains every outer vertex that has not been
completely scanned. Put the other way, when find ap set halts every outer vertex not on a path of
P has been completely scanned. We conclude the following properties when find ap set halts:
(i) Any free vertex ∈
/ V (P) is outer.
(ii) Any edge uv with u outer and u, v ∈
/ V (P) has v inner or Bu = Bv .
Note that (ii) depends on Lemma A.4.
Now consider any alternating path P that is disjoint from V (P) and starts at a free vertex
f . We claim that every vertex of P is inner or outer. Furthermore for any outer blossom B with
B ∩ V (P ) 6= ∅, the first vertex of P in B is the base of B, which is either f or the mate of an inner
vertex.
To prove the claim we argue by induction on the length of P . The claim holds if P is just
the starting vertex f , by (i). Inductively assume P has reached an outer vertex x, having already
reached b(x). If the next vertex y is outer (ii) shows b(y) = b(x). If y is not outer (ii) shows it is
inner. Furthermore y is followed by mate(y), which is the base of its blossom Bmate(y) .
Now observe that P does not contain a free vertex f 0 6= f . In proof, f 0 is outer. The claim
shows P must enter Bf 0 on its base b and b 6= f 0 . But f 0 is the base of any blossom containing it.
Hence f 0 ∈
/ P . We have shown that no augmenting path is disjoint from V (P), as desired.
We close this section with two high-level properties of find ap set that lead to its linear time
bound.
First, any edge is scanned at most twice, once from each end. In proof observe the call find ap(x)
occurs when x becomes a new outer vertex. Thus find ap is called at most once for any given vertex
x∈V.
Second, the test of line 3 is convenient to prove correctness of the algorithm, but is not straightforward to implement. The test of the comment is easily implemented. Appendix A shows the two
tests are equivalent.

5

The data structure

This section gives the data structures that show Phases 1 and 2 both use time O(m). Thus the
√
entire algorithm runs in time O( nm).
10

The matching is represented using an array mate, where any vertex v on matched edge vv 0 has
mate(v) = v 0 . The forest S − is represented using a pointer `(v) for every outer vertex v ∈ V .
Specifically a grow step adds y and y 0 to S − by setting `(y 0 ) = x.
We now discuss each step of our algorithm in turn, presenting the data structure for it and
verifying that linear time is achieved. We begin with Phase 1. Grow steps are trivial.
Blossom steps We find the fundamental cycle C of edge xy in time O(|C|) by climbing the paths
from Bx and By to the root in parallel. This is accomplished using mate and ` pointers, and a data
structure to find the base of a blossom Bx given an arbitrary vertex x.
The data structure is the incremental-tree set-merging algorithm of Gabow and Tarjan [3]. The
operation f ind(x) returns the base vertex of Bx . union operations are used to contract C. The
incremental-tree version of [3] works on a tree that grows by addition of leaves, so it works correctly
on S − . The time for O(m) f inds and O(n) unions is O(m + n) and the space is O(n).
Dual adjustment steps It is well-known how to implement dual adjustment steps efficiently
using (a) the parameter ∆, defined as the current sum of all dual adjustment quantities δ so far;
and (b) an appropriate priority queue.
Our choice for (b) depends on the fact that ∆ is always an integer ≤ n/2. We first prove the
upper bound. At any point in the algorithm let P be any augmenting path. Lemma 3.1 shows
w(P ) ≤ 2y(f ). Then using (3.2) gives
n − 1 ≥ |P | = −w(P ) + 1 ≥ −2y(f ) + 1.
Rearranging gives y(f ) ≥ 1 − n/2. Since y values are initially 1, this implies ∆ ≤ n/2.
To prove integrality we claim that all the y(v) values, v ∈ V (S), are always integers of the same
parity. (Since a free vertex f has y(f ) = 1 − ∆ this implies ∆ is integral.) The claim holds initially
by (A0 ). In the definition of δ in Fig.2, any edge e has y(e) − w(e) = y(e) an even integer. So the
set defining δ consists of integers, and δ is integral. The adjustment of y values in Fig.2 keeps all
values y(v), v ∈ V (S) integers of the same parity.
Now we sketch the algorithm and data structure. The priority queue consists of a collection of
lists L(d), each containing the edges that become tight when ∆ has increased to d. To get the next
edge for the search lists L(∆0 ) are examined, for ∆0 = ∆, ∆ + 1, . . ., until an edge that triggers a
grow, blossom, or augment step is found. This also gives the next value of ∆.
Suppose a grow or blossom step makes vertex u ∈ V outer. Every unmatched edge e = uv is
scanned. e is added to list L(∆ + d) where d is y(e) if v ∈
/ V (S) or y(e)/2 if v is outer.
The next two steps are implemented using the representation RB for every maximal blossom
B. In the data structure for RB , the children of any node B 0 form a doubly linked ring. Each link
also records the edge xy ∈ E that joins the two subblossoms.
Constructing graph H The first task is to identify the blossoms that become vertices of H,
i.e., the blossoms that are maximal immediately before the last dual adjustment. During Edmonds’
search each blossom is marked with the value of ∆ when it is formed. When the search ends each
representation RB is traversed top-down, and blossoms with the final value of ∆ are discarded. The
remaining roots of RB representations are the maximal positive blossoms that become vertices of
V (H).
To construct E(H), we continue the top-down traversal and label every vertex of V with the
V (H) vertex containing it. Then every edge e ∈ E is scanned and added to E(H) if it is tight and
11

joins distinct V (H) vertices, at least one being outer. (z values are not needed for these edges.)
H is represented as an adjacency structure, and the vertex labels are used to add e to the two
appropriate adjacency lists. e also records its preimage in G, so augments can be performed in G.
Turning to Phase 2, the blossom base function b is maintained as in Phase 1 using incrementaltree set-merging.
Computing P (x) in find ap First observe that an RB data structure allows a path P (v, b) to
be computed in time O(|B|) by following the recursive procedure sketched in Section 3.1. This
suffices for our applications, since an augmenting path passes through a maximal blossom at most
once. (In Phase 2 if an augmenting path passes through a blossom B, the vertices of B never get
re-explored.) A more careful approach computes P (v, b) in time linear in its length. The idea is
not to start at the root of RB (as in Section 3.1) but rather start at the node whose child contains
the matched edge incident to v.
find ap builds RB representations for the blossoms it creates. They are used to compute the
augmenting paths yP (x). These paths are then converted to paths in G by adding in P (v, b) paths
that traverse blossom-vertices of H. This is done using the RB representations from Phase 1.
Combining our correctness proof and the above data structures giving linear time, our goal is
achieved:
√
Theorem 5.1 A maximum cardinality matching can be found in time O( nm) and space O(m).

References
[1] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver, Combinatorial Optimization, Wiley and Sons, NY, 1998.
[2] J. Edmonds, “Maximum matching and a polyhedron with 0,1-vertices”, J. Res. Nat. Bur.
Standards 69B, 1965, pp. 125–130.
[3] H.N. Gabow and R.E. Tarjan, “A linear-time algorithm for a special case of disjoint set union”,
J. Comp. and System Sci., 30, 2, 1985, pp. 209–221.
[4] H.N. Gabow and R.E. Tarjan, “Faster scaling algorithms for general graph matching problems”, J. ACM 38, 4, 1991, pp. 815–853.
[5] A.V. Goldberg and A.V. Karzanov, “Maximum skew-symmetric flows and matchings”, Math.
Program., Series A 100, 2004, pp. 537–568.
[6] J.E. Hopcroft and R.M. Karp, “An n2.5 algorithm for maximum matchings in bipartite graphs”,
SIAM J. Comput., 2, 1973, pp. 225–231.
[7] A.V. Karzanov, “On finding maximum flows in network with special structure and some applications”, in Russian, Math. Problems for Production Control 5, Moscow State University
Press, 1973, pp. 81–94.
[8] E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.

12

p
[9] S. Micali and V.V. Vazirani, ”An O( |v| · |E|) algorithm for finding maximum matching in
general graphs”, Proc. 21st Annual Symp. on Found. of Comp. Sci., 1980, pp. 17–27.
[10] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity,
Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982.
[11] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, NY, 2003.
[12] V.V.
√ Vazirani, “A theory of alternating paths and blossoms for proving correctness of the
O( V E) general graph maximum matching algorithm”, Combinatorica, 14, 1, 1994, pp. 71–
109.
[13] V.V. Vazirani, “A simplification of the MV matching algorithm and its proof”,
arXiv:1210.4594v5, Aug.27, 2013, 32 pages; also “A proof of the MV matching algorithm”,
manuscript, May 13, 2014, 42 pages.

13

A

Analysis of find ap set

We will consider S − to be an ordered tree, where grow steps add the children of an outer vertex in
left-to-right order. We also assume S inherits this order. (Thus in Fig.5(b) vertex 3 became outer
after vertex 2.)
Lemma A.1 Any outer vertex r that is not completely scanned has b(r) on the rightmost path of
S −.
Example: The blossom step of Fig.5(b) makes vertex 8 outer but not completely scanned. 8 is
not on the rightmost path of S − but b(r) = 3 is.
Proof: A simple induction shows that when a vertex x is made outer, every vertex s ∈ P (x) has
b(s) on the rightmost path of S − . Recall invariant (I) says whenever find ap(x) scans an edge, P (x)
contains every outer vertex r that has not been completely scanned. So b(r) is on the rightmost
path of S − .
2
Lemma A.2 At any point in the algorithm, consider an edge rs where r is outer and s ∈ V (S).
Either s is inner and left of r in S − , or b(r) and b(s) are related in S − .
Example: Consider edge 8,6 immediately after the blossom step forming Fig.5(b). b(8) = 3 is
related to b(6) = 6 in S − . But 8 itself is not related to 6 in S − . Neither is 5, the mate of 8.
Proof: We will show that every grow and blossom step preserves the lemma. We start with this
preliminary observation: Once an outer vertex r has been completely scanned, any adjacent vertex
s is in S.
Consider a grow step. It adds new vertices y, y 0 , with b(y) = y, b(y 0 ) = y 0 .
Subcase r 6= y 0 : If r is not completely scanned, Lemma A.1 implies b(r) is related to both b(y)
and b(y 0 ). If r is completely scanned the preliminary observation shows s was in S before the grow
step. So s 6= y, y 0 . We conclude the lemma is preserved.
Subcase r = y 0 : Since r is the rightmost vertex of S − , any vertex is either related to r or to the left
of r. So the lemma holds if s is inner. If s is outer it cannot be left of r, since then the preliminary
observation shows r was in S before the grow step.
Now consider a blossom step. We consider the possibilities for r.
Subcase r is a vertex whose b-value is changed to b(x): (These are the vertices that enter Bx .)
Any vertex s has b(s) either related to b(x) or left of b(x) (b(x) is on the rightmost path by Lemma
A.1. So we can assume b(s) is left of b(x). This implies s is also left of b(x). s cannot be outer (as
before, s is completely scanned, so r would be in S before it becomes a descendant of b(x)). So s
is inner as desired.
Subcase r is outer and b(r) is not changed to b(x): We can assume s is a vertex that enters Bx .
We can further assume b(r) is not related to b(s) = b(x). Thus b(r) is to the left of b(x). As before
r is completely scanned, making s in S before it becomes a descendant of b(x).
2

14

Lemma A.3 At any point in the algorithm let t be an inner vertex, whose outer mate t0 is completely scanned, and s an inner S − -descendant of t. A blossom step that makes s outer makes
b(s) = b(t).
Proof: Let P be the S − -path from t to s. We prove the lemma by induction on |P |.
Among all the inner vertices on P , let u be the first to become outer in a blossom step. (If
there is more than one choice take u as deep as possible.) Let that blossom step be triggered by
edge xy where b(x) is an ancestor of b(y). u is an S − -ancestor of b(y) and b(x) is an ancestor of u.
Every outer vertex r on P is completely scanned, since t0 is. (This follows since r became outer
while find ap(t0 ) was executing.) So b(x) is not on P . Thus b(x) is a proper ancestor of t. Letting
u0 be the mate of u, the blossom step sets
(A.1)

b(t) = b(u) = b(u0 ).

If u = s we are done. Otherwise let v be the inner vertex that follows u on P . Let v 0 be its
mate. As already mentioned, v 0 is completely scanned. So the inductive assertion holds for v and
s. Consider the blossom step that makes s outer. Let b1 denote the b function at the end of this
step. The inductive assertion shows
b1 (v) = b1 (s).
Since v was inner, we also have b1 (v) = b1 (u0 ). (A.1) implies b1 (t) = b1 (u0 ). Combining equations gives b1 (t) = b1 (s). This completes the induction.
2
Lemma A.4 At any point in the algorithm, let rs be an edge that has been scanned from both its
ends. Then b(r) = b(s).
Proof: Whenever r and s are both outer, b(r) and b(s) are related in S − (Lemma A.2). Let b(r)
be an ancestor of b(s) the first time both are outer. Although b(r) and b(s) may change over time,
b(r) will always be an ancestor of b(s).
Consider the three possibilities for s when rs is scanned from r.
Case s is not in the search forest: A grow step makes s an inner child of r. Eventually s becomes
outer in a blossom step. The new blossom has an outer base vertex, so the blossom includes r, i.e.,
b(r) = b(s).
Case s is outer: Clearly a blossom step is executed, making b(r) = b(s).
Case s is inner: When rs is scanned from r let t be first inner vertex on the S − -path from b(r) to
s. When r scans rs, t0 = mate(t) is completely scanned. Now apply Lemma A.3 to t and s. The
blossom step that makes s outer makes b1 (t) = b1 (s). Since t has become outer b1 (t) = b1 (r). Thus
b1 (s) = b1 (r) as desired.
2
To implement the algorithm efficiently we change the test for a blossom step, line 3, to the test
of the comment. We will show the two tests are equivalent, i.e.,
b(y) is an outer proper descendant of b(x) in S − iff b(y) became outer strictly after b(x).
To prove the if direction assume b(x) and b(y) are both outer. As blossom bases they both
became outer when they were added to S. Edge xy makes b(x) and b(y) related (Lemma A.2). So
if b(y) was made outer strictly after b(x) it was added to S after b(x), i.e., it descends from b(x).
Thus the condition of line 3 holds.
The only if direction is obvious, since any vertex is added to S − after its ancestors.
15

B

Searching from the middle

The algorithm of Micali and Vazirani [9] is based on a “double depth-first search”: This search
begins at an edge e = uv. It attempts to complete an augmenting path using disjoint paths from
each of u and v to a free vertex. This is done with two coordinated depth-first searches, one starting
at u, the other at v.
The key fact for this approach is a characterization of the starting edge e. We will begin by
describing the conditions satisfied by e, using our terminology. Then we prove that any augmenting
path contains such an edge e. Then we discuss the implications of this structure, including how
the DDFS of [9] can be used for our Phase 2.
We start with terminology based on the state of the search immediately before the last dual
adjustment. Let T 0 be the set of edges of G that are tight at that time. Let D1 ∪ D2 be the set of
edges that become tight in the last dual adjustment, where D1 refers to a grow step and D2 is for a
blossom step. So e ∈ D1 has y 0 (e) = δ with one end of e outer and the other not in S. e ∈ D2 has
y 0 (e) = 2δ with both ends of e outer. (Recall w(e) = 0.) Here y 0 is the dual function right before
the last dual adjustment, and “outer” and S also refer to that time.
Lemma B.1 Any maximum weight augmenting path can be written as
P1 , Q, P2
where
each Pi is an even length alternating path from a free vertex to an outer vertex, Pi ⊆ T 0 ,
Q has the form (e) with e ∈ D2 , or (g1 , e, g2 ) with g1 , g2 ∈ D1 .
Remark: Clearly e is unmatched in the first form and matched in the second. Neither end of e is
in S in the matched form.
Proof: Let y be the final dual function. The dual adjustment step shows that any free vertex f has
y(f ) = y 0 (f ) − δ. As mentioned in the proof of Corollary 3.2 an augmenting path P has maximum
weight iff w(P ) = 2y(f ). Thus
(B.1)

w(P ) = 2y 0 (f ) − 2δ.

Furthermore the corollary shows that for any positive blossom B, P ∩ γ(B) is an even length
alternating path, so z(B) makes no net contribution to w(P ). Thus P contains edges that are not
tight in y 0 , in fact these edges belong to D1 ∪ D2 and have total slack 2δ.
Suppose P contains an edge e ∈ D2 . Since y 0 (e) = 2δ, P contains exactly 1 such edge. The
properties of the lemma for both Pi and Q follow easily.
The other possibility is that P contains exactly two edges g1 , g2 ∈ D1 . Each gi is unmatched
and has an end vi ∈
/ S. P must contain a v1 v2 -subpath of edges in T 0 . It must consist of just one
edge v1 v2 ∈ M , since unmatched edges with no end in S are not tight. The properties of the lemma
for both Pi and Q follow.
2
It may not be clear how find ap succeeds in ignorance of this structure. So we take a more
detailed look. We start with a simple fact:
Proposition B.2 No edge uv ∈ T 0 joins 2 inner vertices.
Proof: A grow step that makes u inner has y(u) = 1. Every subsequent dual adjustment increases y(u). So the search ends with y(u) ≥ 1. If u and v are inner then uv ∈
/ M , and
16

2

y(u) + y(v) ≥ 2 > w(uv) = 0.

We now present a more detailed proof of the lemma. Consider the search graph S immediately
before the last dual adjustment. S is a subgraph of H. Define a path form similar to the lemma,
as
P, Q, P 0
where
P is an even length alternating path from a free vertex to an outer vertex of S, P ⊆ T 0 ;
Q has the form of the lemma;
P 0 is an odd alternating path whose last edge is matched and last vertex is inner in S, P 0 ⊆ T 0 .
Let A be an alternating even-length path in H that starts at a free vertex. We claim that A is
a prefix of the above form. Clearly the claim forces find ap to find a path with the structure of the
lemma.
We prove the claim inductively. Suppose an even length prefix A0 of A ends at vertex u, and
the next two edges of A are uv, vv 0 with uv ∈
/ M 3 vv 0 .
0
0
If A has length 0 then u is free. A has the form P .
Suppose A0 has form P . There are three possibilities:
Subcase v is inner in S: Its mate v 0 is outer, so form P holds for the longer prefix.
Subcase v is outer in S: uv joins two outer vertices of S. Thus uv ∈ D2 . The matched edge vv 0
joins an outer vertex with an inner, so v 0 is inner. So the new prefix of A has form P, Q, P 0 for
P 0 = (vv 0 ).
Subcase v ∈
/ S: This makes uv ∈ D1 . The new prefix has the form P, g1 , e with g1 , e as in Q.
Now suppose A0 has form P, g1 , e with g1 , e as in Q. Since e ∈
/ S and uv is tight, uv ∈ D2 . So
0
0
v is outer. Thus v is inner. The new prefix has form P, Q, P (P 0 = (vv 0 )).
Finally suppose A0 has form P, Q, P 0 . No end of an edge of D1 ∪ D2 is inner. Since u is inner
this makes uv ∈ T 0 . Also u inner makes v outer (Proposition B.2). The new prefix ends with edge
vv 0 ∈ M and v 0 inner. Thus it has form P, Q, P 0 . The induction is complete.
The lemma opens up the possibility of having a Phase 2 search start from an edge e of type Q.
DDFS uses this strategy.
The Micali-Vazirani algorithm uses DDFS in Phase 1 as well. This depends on the fact that
blossoms have a starting edge e similar to the lemma. (More precisely suppose a blossom step
creates a blossom B with base b, with v ∈ B a new outer vertex. Then P (v, b) contains a unique
subpath of form Q of the lemma. This is easily proved as above, e.g., use the second argument,
traversing the path P (v, b) starting from b.)
Using DDFS in both Phases 1 and 2 makes the Micali-Vazirani algorithm elegant and avoids
any overhead in transitioning to Phase 2.
The proof of [13] that DDFS is correct is involved. Possibly it could be simplified using the
lemmas we have presented, as well as other structural properties that weighted matching makes
clear. The following aspects of the finer structure of H are not needed for our development but are
used in [13].
[13] defines evenlevel(x) as the length of a shortest even alternating path from a free vertex to x.
The proof of Lemma 3.1 shows any even alternating f x-path has length ≥ y(x)−y(f ). Furthermore
it shows that an outer vertex x has evenlength(x) = y(x) − y(f ) = |P (x)|.
17

oddlevel(x), the length of a shortest odd alternating path from a free vertex to x,
Phas a similar
characterization, e.g., any odd alternating f x-path has length ≥ 1 − y(x) − y(f ) + z(B), where
the sum extends over blossoms B with base vertex b and x ∈ B − b.
Finally [13] divides the edges of H into bridges and props. This is due to the fact that an edge
e of form Q can trigger an initial blossom step, which can be followed by blossom steps triggered
by unmatched edges of T 0 . e is a bridge and the other triggers are props. (In the precise blossom
structure stated above, e is the Q edge and the prop triggers are in T 0 .)

18

