Data Structures for Weighted Matching and Extensions to
b-matching and f -factors∗

arXiv:1611.07541v1 [] 22 Nov 2016

Harold N. Gabow†
December 18, 2014; revised August 28, 2016

Abstract
This paper shows the weighted matching problem on general graphs can be solved in time
O(n(m+n log n)) for n and m the number of vertices and edges, respectively. This was previously
known only for bipartite graphs. The crux is a data structure for blossom creation. It uses a
dynamic nearest-common-ancestor algorithm to simplify blossom steps, so they involve only
back edges rather than arbitrary nontree edges.
The rest of the paper presents direct extensions of Edmonds’ blossom algorithm to weighted
b-matching and f -factors. Again the time bound is the one previously known for bipartite
graphs: for b-matching the time is O(min{b(V ), n log n}(m + n log n)) and for f -factors the time
is O(min{f (V ), m log n}(m + n log n)), where b(V ) and f (V ) denote the sum of all degree constraints. Several immediate applications of the f -factor algorithm are given: The generalized
shortest path structure of [21], i.e., the analog of the shortest path tree for conservative undirected graphs, is shown to be a version of the blossom structure for f -factors. This structure is
found in time O(|N |(m + n log n)) for N the set of negative edges (0 < |N | < n). A shortest
T -join is found in time O(n(m + n log n)), or O(|T |(m + n log n)) when all costs are nonnegative.
These bounds are all slight improvements of previously known ones, and are simply achieved by
proper initialization of the f -factor algorithm.

1

Introduction

This paper solves a well-known problem in data structures to achieve an efficient algorithm for
weighted matching. It also extends the results to the most general weighted matching problems.
This section defines the problems and states the results.
A matching on a graph is a set of vertex-disjoint edges. A matching is perfect if it covers every
vertex. More generally it is maximum cardinality if it has the greatest possible number of edges,
and cardinality k if it has exactly k edges. Let each edge e have a real-valued weight w(e). The
weight w(S) of a set of edges S is the sum of the individual edge weights. Each of the above variants
has a maximum weight version, e.g., a maximum weight matching has the greatest possible weight,
a maximum weight perfect matching has maximum weight subject to the contraint that it is perfect,
etc. Alternatively edges may have real-valued costs, and we define minimum cost matching, etc.
The weighted matching problem is to find a matching of one of these types, e.g., find a maximum
∗
This paper is a combination of two conference papers: A preliminary version of the data structures part appeared
in Proc. 1st Annual ACM-SIAM Symp. on Disc. Algorithms, 1990 [15]. A preliminary version of the extensions part,
based on reduction to matching, appeared in Proc. 15th Annual ACM Symp. on Theory of Comp., 1983 [13].
†
Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado 80309-0430, USA.
Research supported in part by NSF Grant No. CCR-8815636. E-mail: hal@cs.colorado.edu

1

weight perfect matching on a given graph, etc. All these variants are essentially equivalent from
an algorithmic viewpoint. For definiteness this paper concentrates on maximum weight perfect
matching.
In stating resource bounds for graph algorithms we assume throughout this paper that the given
graph has n vertices and m edges. For notational simplicity we assume m ≥ n/2. In the weighted
matching problem this can always be achieved by discarding isolated vertices.
Weighted matching is a classic problem in network optimization; detailed discussions are in
[27, 29, 33, 34, 5]. Edmonds gave the first polynomial-time algorithm for weighted matching [9].
Several implementations of Edmonds’ algorithm have been given with increasingly fast running
times: O(n3 ) [11, 27], O(mn log n) [4, 20], O(n(m log log log 2+m/n n + n log n)) [18]. Edmonds’
algorithm is a generalization of the Hungarian algorithm, due to Kuhn, for weighted matching on
bipartite graphs [25, 26]. Fredman and Tarjan implement the Hungarian algorithm in O(n(m +
n log n)) time using Fibonacci heaps [10]. They ask if general matching can be done in this time.
We answer affirmatively: We show that a search in Edmonds’ algorithm can be implemented in
time O(m + n log n). This implies that the weighted matching problem can be solved in time
O(n(m + n log n)). The space is O(m). Our implementation of a search is in some sense optimal:
As shown by Fredman and Tarjan [10] for Dijkstra’s algorithm, one search of Edmonds’ algorithm
can be used to sort n numbers. Thus a search requires time Ω(m + n log n) in an appropriate model
of computation.
Weighted matching algorithms based on cost-scaling have a better asymptotic time bound
when costs are small integers [23]. However our result remains of interest for at least two reasons:
First, Edmonds’ algorithm is theoretically attractive because its time bound is strongly polynomial.
Second, for a number of matching and related problems, the best known solution amounts to
performing one search of Edmonds’ algorithm, e.g., most forms of sensitivity analysis for weighted
matching [4, 8, 14, 38]. Thus our implementation of a search in time O(m + n log n) gives the
best-known algorithm for these problems.
The paper continues by presenting versions of Edmonds’ blossom algorithm for weighted bmatching and weighted f -factors. These problems generalize ordinary matching to larger degreeconstrained subgraphs and are defined as follows. For an undirected multigraph G = (V, E) with
function f : V → Z+ , an f -factor is a subgraph where each vertex v ∈ V has degree exactly f (v).
For an undirected graph G = (V, E) where E may contain loops, with function
b : V → Z+ , a
P
(perfect) b-matching is a function x : E → Z+ where each vertex v ∈ V has w:vw∈E x(vw) = b(v).
Given in addition a weight function w : E → R, a maximum b-matching is a (perfect) b-matching
with the greatest weight possible; similarly for maximum f -factor. We find maximum b-matchings
and f -factors in the same time bound as was known for bipartite graphs: for b-matching the time
is O(min{b(V ), n log n}(m + n log n)) where b(V ) is the sum of all degree constraints; for f -factors
the time is O(min{f (V ), m log n}(m + n log n)) where f (V ) is the sum of all degree constraints. A
blossom algorithm for b-matching is given in Pulleyblank’s thesis [31] ([32] gives a very high level
description, different from our algorithm). The pseudo-polynomial parts of the above bounds (i.e.,
the bounds using b(V ) and f (V )) can also be achieved using the current paper’s algorithm for
ordinary matching plus the reduction to matching presented in the original version of the current
paper [13].
Here we prefer direct implementations of the general matching algorithms, to avoid practical
inefficiencies and to illuminate the properties of blossoms. As an example of the latter, the algorithm’s blossom structure is shown to be exactly the generalized shortest path structure of Gabow
and Sankowski [21], i.e., the analog of the shortest path tree for conservative undirected graphs.
(The paths in blossoms that are used to augment the matching give the shortest paths to the fixed
source in a conservative undirected graph.) Our discussion of blossoms also leads to (and requires)
2

simple proofs of (previously known) min-max formulas for the maximum size of a b-matching, equation (4.5), or partial f -factor, (5.6). Lastly our algorithm shows that b-matching blossoms have
the same structure as ordinary matching blossoms (unlike f -factors there are no “I(B)-sets”, i.e.,
pendant edges, and no ”heavy blossoms”, only “light” ones, at least in the final output).
We find the generalized shortest path structure in time O(|N |(m + n log n)) for N the set of
negative edges (0 < |N | < n for conservative costs) and a shortest T -join in time O(n(m + n log n)),
or O(|T |(m + n log n)) for nonnegative costs. These bounds are slight improvements of previously
known ones and are achieved simply by proper initialization of the f -factor algorithm. (The strong
polynomial bound of Gabow and Sankowski [21, Section 10] can be modified to achieve the same
time as ours for the matching part, plus additional time O(m log n) for post-processing.) Good
implementations of the T -join algorithm of Edmonds use time O(n3 ) for general costs and the
same time as ours plus O(|T |3 ) for nonnegative costs, both cubic terms coming from finding a
minimum cost matching on a complete graph [34, p.486 and p.488].)
The paper is organized as follows. This section concludes with some terminology and assumptions. Section 2 reviews Edmonds’ algorithm and defines the “blossom-merging problem” – the
last ingredient needed to obtain the time bound we seek. Section 3 specializes this problem to
“tree-blossom-merging” and solves it. Section 4 gives our b-matching algorithm and Section 5 gives
the f -factor algorithm. Appendix A gives further details of Edmonds’ matching algorithm. Appendix B gives some further details for b-matching and f -factors. Appendix C gives an efficient
implementation of the grow and expand steps of Edmonds’ algorithm. Gabow [14] gives a faster
algorithm, but Appendix C is simpler and suffices to achieve our overall time bound. Appendix C
also gives the details for grow and expand steps for b-matching and f -factors. The latter is more
involved but follows the same outline.
Our algorithm for tree-blossom-merging requires an algorithm that computes nearest common
ancestors in trees that grow by addition of new leaves. The conference version of this paper
[15] presented the required algorithm, as well as extensions. For reasons of succinctness the data
structure for nearest common ancestors is now given separately in [16].
Portions of this paper may be read independently. Our implementation of Edmonds’ matching
algorithm is in Section 3; readers familiar with Edmonds’ algorithm can skip the review in and go
directly to Section 2.3. Those interested in generalized versions of matching should concentrate
on f -factors, our most general algorithm (Section 5), although some basic lemmas are proved in
Section 4.
History of this paper The conference paper [15] presented a preliminary version of the treeblossom-merging algorithm. The current paper simplifies that algorithm, e.g., there is no need to
refine the strategy for sparse graphs (m = o(n log 2 n). The tree-blossom-merging algorithm uses an
algorithm that computes nearest common ancestors in trees that grow by addition of new leaves.
[15] presented the required algorithm, as well as extensions. As mentioned this is now given in [16].
Subsequent to [15] Cole and Hariharan [6] used a similar approach to allow other operations; they
also achieve time bounds that are worst-case rather than amortized.
The results on b-matching and f -factors evolve from the conference paper [13]. That paper
achieved similar time bounds to those presented here by reducing the problems to matching. The
current paper gives direct approaches to the problems, thus illuminating the structure of blossoms
(see Sections 4.1 and 5.1) and avoiding the blow-up in problem size incurred by reduction.
Terminology We often omit set braces from singleton sets, denoting {v} as v. We use interval
notation for sets of integers: for i, j ∈ Z, [i..j] = {k∈Z : i ≤ k ≤ j}. We use a common summing

3

P
notation: If x is a function on elements and S a set of elements then x(S) denotes s∈S x(s). log n
denotes logarithm to the base two. Assume that for a given integer s ∈ [1..n] the value ⌊ log s⌋ can
be computed in O(1) time. This can be done if we precompute these n values and store them in a
table. The precomputation time is O(n).
For a graph G, V (G) denotes its vertices and E(G) its edges. For vertices x, y an xy-path has
ends x and y. For a set of vertices S ⊆ V and a subgraph H of G, δ(S, H) (γ(S, H)) denotes the
set of edges with exactly one (respectively two) endpoint in S. (Loops are in γ but not δ.) d(v, H)
denotes the degree of vertex v in H. When referring to the given graph G we often omit the last
argument and write, e.g., δ(S). (For example a vertex v has d(v) = |δ(v)| + 2|γ(v)|.)
Fix a matching M on the given graph. 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

Edmonds’ algorithm and its implementation

This section summarizes Edmonds’ algorithm and known results on its implementation. Sections
2.1–2.2 sketch the high level algorithm. They include all the details needed for our implementation
but do not give a complete development. For the latter see, e.g., [9, 11, 27, 33]. Section 2.3 reviews
the portions of the algorithm for which efficient implementations are known, and the outstanding
problem of efficient “blossom merging”.

2.1

Blossoms

Throughout this section the notation P (x, y) denotes an xy-path. This includes the possibility that
x = y, i.e., P (x, x) = (x).
Edmonds’ algorithm is based on the notion of blossom. We start with a data-structure-oriented
definition, illustrated in Fig. 1. Begin by considering two even-length alternating paths P (xi , y),
i = 0, 1, with x0 6= x1 and y the only common vertex. Each path begins with the matched edge at
xi , unless xi = y. These paths plus an edge x0 x1 form a simple example of a blossom. Edmonds’
algorithm contracts blossoms. This leads to the general, recursive definition:
Definition 2.1 Let G be a graph with a distinguished matching. A blossom is a subgraph defined
by rules (a) and (b):
(a) Any single vertex b is a blossom.
(b) Let G be a graph formed from G by contracting zero or more vertex-disjoint blossoms. Let
X0 , X1 , Y be G-vertices, X0 6= X1 . For i = 0, 1 let P (Xi , Y ) be an even-length alternating path that
starts with a matched edge or has Xi = Y , with Y the only common G-vertex. These paths plus an
edge X0 X1 form a blossom.
In Fig. 1 blossom B is formed from paths P (B4 , B0 ), P (B6 , B0 ) and edge γ. We use the term
“vertex” to refer to a vertex of the given graph G. For a blossom B, V (B) is the set of vertices of
G contained in any blossom in either path P (Xi , Y ); we sometimes refer to them as the vertices of
B. The maximal blossoms in the paths P (Xi , Y ) are the subblossoms of B.
We use some properties of blossoms that are easily established by induction. Any blossom has
a base vertex: In Definition 2.1 a blossom of type (a) has base vertex b. A blossom of type (b) has
the same base vertex as Y . We usually denote the base of B as β(B) (or β if the blossom is clear).
4

B
B0
α
B1

a = a0
A

a1
a2

ε

B5

a3
a4

δ

B2

B6

c

B3

γ

B4

Figure 1: Blossoms in a search of Edmonds’ algorithm. Blossom B is formed from subblossoms
B0 , . . . , B6 . Heavy edges are matched.
β(B) is the unique vertex of B that is not matched to another vertex of B. β(B) is either free or
matched to another vertex not in B. We call B a free blossom or matched blossom accordingly.
Consider a blossom B with base vertex β. Any vertex x ∈ V (B) has an even-length alternating
path P (x, β) that starts with the matched edge at x. (P (β, β) has no edges.) For example in Fig.1 in
blossom B, P (a, β(B)) starts with P (a, β(B1 )) = (a0 , a1 , a2 , a3 , a4 ) followed by edge (β(B1 ), β(B2 ))
and the reverse of P (c, β(B2 )), and continuing along paths in B3 , B4 , B6 , B5 , B0 .
To define P (x, β) in general consider the two paths for B in Definition 2.1. Among the blossoms
in these paths let x belong to a blossom designated as B0 . The edges of B (i.e., the edges of P (Xi , Y )
plus X0 X1 ) contain a unique even-length alternating path A from B0 to Y . Here A is a path in G.
First suppose B0 6= Y . A starts with the matched edge at B0 . P (x, β) passes through the same
blossoms as A. To be precise let the G-vertices of A be Bi , i = 0, . . . , k, Bk = Y , with k > 0 even.
Let βi be the base vertex of Bi . So there are vertices xi ∈ V (Bi ) such that the edges of A are
β0 β1 , x1 x2 , β2 β3 , x3 x4 , . . . , xk−1 xk .
Here the βi βi+1 edges are matched and the xi xi+1 edges are unmatched. Recursively define P (x, β)
as the concatenation of k + 1 subpaths
(2.1)

P (x, β) = P (x, β0 ), P (β1 , x1 ), P (x2 , β2 ), P (β3 , x3 ), . . . , P (xk , βk ).
5

For odd i, P (βi , xi ) is the reverse of path P (xi , βi ).
Now consider the base case B0 = Y . If Y is a vertex then Y = x = β and P (x, β) = (x).
Otherwise P (x, β) in blossom B is identical to P (x, β) in B0 .1
Edmonds’ algorithm finds an augmenting path P in the graph G that has every blossom contracted. P corresponds to an augmenting path P in the given graph G: For any contracted blossom
B on an unmatched edge xy (x ∈ V (B)) of P , P traverses the path P (x, β(B)). If we augment the
matching of G along P , every blossom becomes a blossom in the new matched graph: For instance
the above vertex x becomes the new base of B. In Fig.1 if P contains an unmatched edge α′ that
enters B at vertex a, P contains the subpath P (a, β(B)). The augment makes a the base of B as
well as B1 ; in the contracted graph α′ is the matched edge incident to B.

2.2

Edmonds’ weighted matching algorithm

For definiteness consider the problem of finding a maximum weight perfect matching. The algorithm
is easily modified for all the other variants of weighted matching. Without loss of generality assume
a perfect matching exists.
The algorithm is a primal-dual strategy based on Edmonds’ formulation of weighted matching
as a linear program. It repeatedly finds a maximum weight augmenting path and augments the
matching. The procedure to find one augmenting path is a search. If the search is successful, i.e.,
it finds an augmenting path P , then an augment step is done. It augments the matching along P .
The entire algorithm consists of n/2 searches and augment steps. At any point in the algorithm
V (G) is partitioned into blossoms. Initially every vertex is a singleton blossom.
The following pseudocode gives a precise specification of the search for an augmenting path; a
more detailed discussion with examples follows. Assume the graph has a perfect matching so this
path exists. For any vertex v, Bv denotes the maximal blossom containing v.
A search constructs a subgraph S. S is initialized to contain every free blossom. It is enlarged by
executing three types of steps, called grow, blossom, and expand steps in [14]. In addition the search
changes the linear programming dual variables in dual adjustment steps. After a dual adjustment
step, one or more of the other steps can be performed. Steps are repeated until S contains the
desired augmenting path.
S consists of blossoms forming a forest. More precisely if each blossom is contracted to a vertex,
S becomes a forest S whose roots are the free blossoms. A blossom of S that is an even (odd)
distance from a root of S is outer (inner). (The third possibility is a blossom not in S.) A vertex
of S is outer or inner depending on the blossom that contains it. Any path from a root to a node
in its tree of S is alternating. So the matched edge incident to a nonroot outer blossom goes to its
parent; the matched edge incident to an inner blossom goes to its unique child.
In Fig. 1 suppose B0 , . . . , B6 are maximal blossoms, edges γ, δ, ε are not part of S, and blossom
B has not yet formed. If B0 is outer, the outer blossoms are the Bi with i even. If a blossom step
forms blossom B, the Bi with i odd change from inner to outer. Now we discuss the three steps
that build up S (see also Fig. 2).
Grow steps A grow step enlarges S. It is executed for an edge vx where vertex v is outer and x is
not in S. Let x be in the maximal blossom B with base vertex β. B is a matched blossom (by the
1

The P (x, β) paths may intersect in nontrivial ways. For instance in Fig. 1, P (β(B3 ), β(B)) and P (β(B5 ), β(B))
traverse edge γ in opposite directions. So the paths have common subpaths, e.g., the subpath of P (β(B5 ), β(B))
joining γ and edge (β(B3 ), β(B4 )), and disjoint subpaths, e.g., the subpath of P (β(B5 ), β(B)) joining β(B3 ) and edge
α. This intersection pattern can continue inside blossom B0 . So in general for two vertices x0 , x1 in a blossom B
with base β, the paths P (xi , β) can have arbitrarily many subpaths that are alternately common and disjoint.

6

make every free vertex or free blossom the (outer) root of an S-tree
loop
if ∃ tight edge e = xy, x outer and y ∈
/ S then
/* grow step */
let β be the base of By , with ββ ′ ∈ M
add xy, By , ββ ′ , Bβ ′ to S
else if ∃ tight edge e = xy, x, y outer in the same search tree, Bx 6= By then
/* blossom step */
merge all blossoms in the fundamental cycle of e in S
else if ∃ tight edge e = xy, x, y outer in different search trees then
/* augment step */
/* xy plus the S-paths to x and y form an augmenting path P */
augment the matching along P and end the search
else if ∃ a nonsingleton inner blossom B with z(B) = 0 then
/* expand step */
let S contain edges xy and ββ ′ incident to B where β is the base of B, x ∈ V (B)
let B have subblossoms Bi
in S replace B by the even length alternating path of subblossoms B0 , . . . , Bk
that has x ∈ B0 , β ∈ Bk
/* the remaining subblossoms of B are no longer in S */
else adjust duals
Figure 2: Pseudocode for a search in Edmonds’ algorithm.

7

initialization of S). Let ββ ′ be the corresponding matched edge. β ′ is the base vertex of a maximal
blossom B ′ . The grow step adds edge vx, B, edge ββ ′ and B ′ to S. B and B ′ are new inner and
outer blossoms respectively.
In Fig. 1 if S contains outer blossom B0 but no other Bi , a grow step for edge α adds α, B1 ,
(β(B1 ), β(B2 )) and B2 to S. Two more grow steps add the other Bi , i = 3, . . . , 6.
Blossom steps A blossom step is executed for an edge e that joins two distinct outer blossoms in
the same tree of S. It combines all blossoms along the fundamental cycle of e to form a new blossom
B. Note that B is outer: In proof let A be the blossom closest to the root in e’s fundamental cycle.
B is outer if A is. If e is incident to A then A is outer, by definition. If e is not incident to A then
the ends of e descend from 2 distinct children of A. A must be outer, since as previously noted any
inner blossom has only one child.
In Fig. 1 suppose S contains blossoms Bi , i = 0, . . . , 6, with Bi outer for i even. A blssom step
for γ would form blossom B. Alternatively the search might do a blossom step for ε, then later one
for δ, and still later one for γ. Other sequences are possible, and the one executed depends on the
costs of these edges.
Expand steps An expand step replaces an inner blossom B of S by some of its subblossoms.
Specifically let B, with base vertex β, be incident to edges xy and ββ ′ in S, with x ∈ V (B). Let x
(β) be in the maximal subblossom B0 (Br ) of B, respectively, and let P (B0 , Br ) be the even-length
alternating path formed from edges of B. Then B is replaced by P (B0 , Br ) in S. The remaining
subblossoms of B are no longer in S – they are now eligible to enter S in grow steps. S remains a
forest.
In Fig. 1 when S contains all blossoms Bi , an expand step for B1 replaces it by vertices a0 , a1 ,
blossom A, a3 , and a4 . The other two subblossoms of B1 leave S.
This completes the description of the three steps that construct S. Note that once a vertex
becomes outer it remains in S and outer for the rest of the search. In contrast vertices can alternate
between being inner and not being in S (perhaps ultimately becoming outer in a grow or blossom
step). This alternation can occur Θ(n) times for a given vertex v in one search (the upper bound n
holds since each time v is involved in an expand step, the size of the maximal blossom containing
v decreases).
The sequence of steps executed by the search depends on the costs of edges and the values of
the dual variables. The algorithm executes a given step when a corresponding edge becomes tight,
i.e., its dual variables satisfy the complementary slackness conditions of linear programming. For
example in Fig. 1 the blossom step for γ is done when γ becomes tight. The dual adjustment step
modifies dual variables so that additional edges become tight and corresponding grow, blossom or
expand steps can be done. The dual adjustment step involves finding a candidate edge that is
closest to being tight, and then changing the dual variables to make it tight. It is given in detail
in Appendix A.
The search terminates in an augment step. It is executed for an edge e that joins 2 different
trees of S. Let e join blossoms X0 and X1 , with Xi in the tree rooted at free blossom Bi . e plus
the edges of S from Xi to Bi forms an augmenting path P in the current contracted graph G. We
augment the matching along the path P in G, as described above. This changes base vertices of
various blossoms on P as well as P .
After an augment the algorithm halts if every vertex is matched. Otherwise the next search is
initialized: Every free blossom is made a tree root of S. Then we proceed as above. Note that the

8

initialization retains all the blossoms – a maximal blossom that is not free is now a blossom not in
S.2
Data structure for blossoms The data structure consists of two parts, both used in most
implementations of Edmonds’ algorithm. The maximal outer blossoms are tracked using a data
structure for set-merging. It suffices to use an algorithm that executes O(m) f inds and O(n)
unions in a universe of n elements in O(m + n log n) total time and O(n) space (e.g., the simple
relabel-the-smaller-set algorithm [1, 7]). The incremental-tree set-merging algorithm of Gabow
and Tarjan [22] improves this to linear time. The set-merging data structure is used to manipulate
the vertices of S, e.g., a blossom step does f inds to identify the outer vertices in the fundamental
cycle in G and unions to contract the cycle. (The inner vertices are identified using the algorithm
of Appendix C, as discussed at the start of Section 2.3.)
The second part of the data structure is based on a forest representing the laminar family of
blossoms. The main use is to compute P (x, β) paths. These paths are used to find augmenting paths, and to compute the supporting forest for tree-blossom-merging (Section 3). The data
structure is also used in expand steps to update S.
The laminar family is defined as follows. Every maximal blossom B ∗ has a corresponding tree
T (B ∗ ). The root of T (B ∗ ) is a node corresponding to B ∗ and the leaves correspond to V (B ∗ ). The
children of any node B are the subblossoms Bi of B. T (B ∗ ) is an ordered tree, with the children
Bi of B ordered according to the edges of B that form a cycle spanning the contracted Bi (in
Definition 2.1 these are the edges of the two paths P (Xi , Y ) plus X0 X1 ).
The data structure for the laminar family has the following components. The root node (for
∗
B ) records the vertex β(B ∗ ). The children of any node B form a doubly linked ring. Each link
also records the edge xy of G (x, y ∈ V (G)) that joins the two subblossoms. Finally T (B ∗ ) has
parent pointers. Additionally we assume the edges of the matching M are marked as such.
This data structure has size O(|V (B ∗ )|) = O(n). In proof the leaves of the tree form the set
V (B ∗ ). Each interior node is a nonsingleton blossom, so there are fewer than |V (B ∗ )| interior
nodes.
The data structure is initially constructed in the blossom step. The expand step involves
replacing the inner node B ∗ with a path formed from the children of B ∗ . The other applications
are based on P (x, β) paths. For completeness we give a routine for computing these paths.
We start with some simple primitive operations. Given x ∈ V (B ∗ ) the blossoms containing x
are identified by tracing the path from the leaf x to the root of T (B ∗ ). An interior node B 6= B ∗
with a link corresponding to edge xy ∈ M , x ∈ V (B) has base vertex x. If neither link from B is
matched then the base vertex of B is that of its first ancestor having an incident matched edge.
We turn to computing the P (x, β) paths. The main algorithm requires P (x, β) in the form
of a list of edges, say L. The supporting forest requires this list to be ordered as an xβ-path.
The following recursive routine uses a global list L. Each recursive invocation enlarges L with the
appropriate edges.
Consider any blossom B (maximal or not) and a vertex x ∈ V (B). The recursive routine adds
the edges of P (x, β(B)) or its reverse to L. The routine is called with 4 arguments:
vertex x and the child B0 of B that contains x;
the base vertex β(B);
a bit r equal to 1 if the reverse path P (β(B), x) is desired, else 0.
2

This contrasts with maximum cardinality matching, where initialization discards the blossoms. As a result there
are no inner blossoms.

9

The following procedure is used if r = 0: First consider the general case B0 6= Bk . Starting at
B0 follow links to the siblings Bi corresponding to the blossoms of (2.1). The last blossom Bk is
identified as the node whose two links both have unmatched edges. For each Bi use a recursive call
to find the corresponding subpath of (2.1), and then for i < k add the edge corresponding to the
link leaving Bi (i.e., βi βi+1 or xi xi+1 ) to L. The arguments for each recursive call P (xi , β(Bi )) are
easily found using the above primitives, with the value of r corresponding to (2.1). (The argument
β(Bi ) is known from the matched edge incident to Bi , for any i < k. For i = k it is known from the
matched edge incident to an ancestor of B, unless β(B) = β(B ∗ ). That base is explicitly recorded
in the data structure.) The base case B0 = Bk is handled as in the definition of P (x, β), i.e.,
immediately return if B0 is a vertex else recurse as above.
Now suppose the routine is called with r = 1. The base case is unchanged. For the general
case first find which of the two links from Bk corresponds to an edge on the desired path. Do this
by following links from B0 to Bk , starting with the appropriate link from B0 . Then follow links
from Bk to B0 , starting with the appropriate link. As in the r = 0 case, issue recursive calls, and
for i > 0 add the edge leaving Bi . The recursive calls have r set to the complement of the bit
corresponding to (2.1).
The arguments for the initial call to find P (x, β(B)) are found as above.
Regarding efficiency first observe that the procedure is easily implemented to use time O(|V (B)|),
as follows. For any recursive call P (xi , β(Bi )) the path-tracing to find the subblossom containing
xi is only done the first time it is needed. Once the path is known it is treated like a stack to get
subsequent subblossoms containing xi .
The time can be improved to O(|P (x, β(B))|). This requires eliminating part of the path-tracing
to find the blossoms containing xi . Specifically we must skip over the smallest blossoms containing
xi as base vertex, since they do not contain any edge of the output P (x, β(B)). To accomplish
this we augment the data structure so each matched edge corresponding to a link in T (B ∗ ) has a
pointer to that link. The path-tracing for xi starts at the link for the matched edge incident to xi .
This bypasses all the unwanted blossoms with base vertex xi .

2.3

The blossom-merging problem

This completes the sketch of Edmonds’ algorithm. Our task is to implement a search in time
O(m + n log n). It is known how to implement most parts within the desired time bound. For
dual adjustment steps a Fibonacci heap F is used. It contains the candidate edges for tightness
mentioned above. The heap minimum gives the next edge to be made tight. This is analogous to
Fredman and Tarjan’s implementation of Dijkstra’s algorithm by Fibonacci heaps and uses the same
time per search, O(m + n log n). Dual variables are maintained in time O(n) per search using offset
quantities (e.g., [20]). The processing associated with grow and expand steps can be done in time
O(mα(m, n)) using a data structure for list splitting given in Gabow [14].3 A simpler algorithm
is presented in Appendix C; it suffices for our time bound and makes this paper self-contained.
The current blossom containing a given vertex is found using the set-merging data structure of last
section for outer vertices and the grow/expand algorithm for nonouter vertices. Finally note after
a successful search, the corresponding augment step can be done in time O(n) using the P (x, β)
paths [12]. This leaves only the blossom steps: implementing the blossom steps of a search in
time O(m + n log n) gives the desired result. (This observation is also made by Gabow, Galil, and
Spencer[18].)
The problem of implementing the blossom steps of a search can be stated precisely as the
3

After the conference version of this paper the time for list splitting was improved by Pettie [30] and Thorup [37].

10

blossom-merging problem which we now define. ([18] defines a similar problem called on-line restricted component merging, solving it in time O(m log log log 2+m/n n + n log n).) The universe
consists of a graph with vertex set O and edge set E, both initially empty. (O will model the set of
outer vertices, E the set of edges joining two O-vertices and thus candidates for blossoms.) At any
point in time O is partitioned into subsets called blossoms. The problem is to process (on-line) a
sequence of the following types of operations:
make blossom(A) – add the set of vertices A to O and make A a blossom
(this assumes A ∩ O = ∅ before the operation);
merge(A, B) – combine blossoms A and B into a new blossom
(this destroys the old blossoms A and B);
make edge(vw, t) – add edge vw, with cost t, to E (this assumes v, w ∈ O);
min edge – return an edge vw of E that has minimum cost subject to the constraint
that v and w are (currently) in distinct blossoms.
Let us sketch how these four operations are used to implement a search. Grow, expand and
blossom steps each create new outer blossoms. They perform make blossom operations to add the
new outer vertices to O. They also perform make edge operations for the new edges that join two
outer vertices. For example in Fig. 1 if B0 , B5 and B6 are in S and a grow step is done for edge α
then make blossom(B2 ) is done; also make edge is done for edge δ. Note that in make edge(vw, t),
t is not the given cost c(vw). Rather t is c(vw) modified by dual values; this modification allows
the algorithm to make dual adjustments efficiently (see e.g., Gabow, Micali, and Galil[20]). The
value of t is unknown until the time of the make edge operation. From now on, since we are only
concerned with the blossom-merging problem, the “cost” of an edge of E refers to this value t, not
the cost input to the matching algorithm.
A blossom step performs merges to construct the new blossom. In Fig. 1 the operations
merge(Bi , B0 ), i = 1, . . . , 6 construct B. Note that information giving the edge structure of blossoms
is maintained and used in the outer part of the algorithm – it is not relevant to the blossom-merging
problem. For this problem a blossom B is identical to its vertex set V (B); the merge operation need
only update the information about the partition of O induced by blossoms. Also in the blossommerging problem “blossom” refers to a set of the vertex partition, i.e., the result of a make blossom
or merge operation. The latter may be only a piece of a blossom in Edmonds’ algorithm (as in the
6 merges above) but this is not relevant.
A min edge operation is done at the end of each of the three search steps. The returned edge,
say e, is used in the above-mentioned Fibonacci heap F that selects the next step of the search.
Specifically F has one entry that maintains the smallest cost edge of E. If that entry already
contains e nothing is done. If the entry contains an edge of larger cost than e, the entry is updated
to e and a corresponding decrease key is done. The smallest key in F (which may or may not be
the key for e) is used for the next dual adjustment and the next step of the search.
To illustrate this process in Fig. 1 suppose O consists of Bi for i = 0, 1, 2, 5, 6 and E = {δ, ε}.
Furthermore the entry in F contains edge δ. A grow step for B3 and B4 adds V (B4 ) to O and
make edge is done for γ. If γ is now the smallest edge in E, the entry in F for the next blossom
step changes from δ to γ and a corresponding decrease key is performed.
Our task is to implement a sequence of these operations: make blossoms adding a total of ≤ n
vertices, ≤ m make edges, ≤ n merges and ≤ n min edges, in time O(m + n log n). The bound
on min edges follows since min edge need not be done after an expand step that does not create
a new outer vertex (e.g., in Fig. 1 with blossom B1 already expanded, expanding A does not add

11

outer vertices). Every other step creates a new outer vertex (a blossom step changes an inner vertex
to outer). So there are at most n such steps and n corresponding min edges.
The difficulty in solving the blossom-merging problem is illustrated by Fig. 1. When each Bi ,
i = 0, . . . , 6 is a blossom, edges γ, δ, ǫ are candidates for min edge. If a blossom step for γ is
done, δ and ǫ become irrelevant – they no longer join distinct blossoms. If we store the edges of
E in a priority queue useless edges like δ, ǫ can end up in the queue. These edges eventually get
deleted from the queue but the deletions accomplish no useful work. The time bound becomes
Ω(m log n). (This also indicates why there is no need for a delete min operation in the blossommerging problem: If edge γ gets returned by min edge and as above a blossom step forms B, edge
γ becomes irrelevant.)

3

Tree-blossom-merging

Tree-blossom merging incorporates the topology of the search graph into general blossom-merging,
in two ways. This section starts by defining the tree-blossom-merging problem and showing how
it can be used to implement the blossom steps of Edmonds’ algorithm. Then it presents our
tree-blossom-merging algorithm.
The first goal is to maintain a representation of the search graph S by a forest that changes as
little as possible. We cannot avoid adding nodes, e.g., in grow steps. But we can define a forest
that does not change in expand steps. Consider a search tree, i.e., a tree T in the forest S.
Definition 3.1 A tree T supports the search tree T if each blossom B of T has a corresponding
subtree TB in T , these subtrees partition the vertices of T and are joined by edges of T , and for
each blossom B:
Case B is outer: Let B have base vertex β. V (B) = V (TB ). If B is incident to the matched edge
ββ ′ in T then β ′ is the parent of β in T . If B is a free vertex then β is the root of T .
Case B is inner: Let B be incident to edges vx, ββ ′ in T , where x, β ∈ V (B) and ββ ′ is matched.
Then TB is the path P (x, β) and v is the parent of x in T .
Take any vertex v in an outer blossom B of T . v has a path to the root in both T and T ,
say pT (v) and pT (v) respectively. Let pT (v) = (B0 = B, B1 , . . . , Bk ). pT (v) consists of subpaths
through each subtree TBi . For even i the subpath contains the base vertex β(Bi ) and perhaps other
Bi -vertices. For odd i the subpath is the entire path TBi . This correspondence will allow us to
track potential blossom steps, as well as execute them, in the supporting forest.
We will maintain the supporting tree T using this operation:
add leaf (x, y) – add a new leaf y, with parent x, to T .
Here we assume x is a node already in T and y is a new node not in T . We also assume the data
structure for T records parent pointers created by add leaf .
We now show how T is maintained as the search algorithm executes grow, blossom and expand
steps. Assume the partition of V (T ) into outer blossoms and individual vertices in inner blossoms
is maintained by a set-merging algorithm.
Suppose a grow step enlarges S by adding unmatched edge vx, inner blossom B, matched edge
ββ ′ and outer blossom B ′ , where vertices v ∈ V (T ), x, β ∈ B and β ′ ∈ B ′ . First compute P (x, β)
and write it as xi , i = 0, . . . , k where x0 = x, xk = β. Enlarge T by performing add leaf (v, x0 ),
12

add leaf (xi , xi+1 ) for i = 0, . . . , k − 1, add leaf (xk , β ′ ) and finally add leaf (β ′ , w) for every w ∈
B ′ − β ′ . Merge the vertices of B ′ into one set. (The search algorithm accesses the vertices of B ′
from the blossom data structure at the end of Section 2.2.)
Consider a blossom step for edge vw. It combines the blossoms on the fundamental cycle C of
vw in T . Let blossom A be the nearest common ancestor of the blossoms containing v and w in T .
A is an outer blossom. C consists of the subpaths of pT (v) and pT (w) ending at A. In T , merge
every outer blossom in C into the blossom A. For each inner blossom B in C, do add leaf (v, u) for
every vertex u ∈ B − V (T ). Then merge every vertex of B into A. The new blossom A has the
correct subgraph TA so the updated T supports T .
Lastly consider an expand step. The expand step in the search algorithm replaces an inner
blossom B by the subblossoms along the path P (x, β), say subblossoms Bi , i = 0, . . . , k, where
x ∈ B0 and β ∈ Bk . By definition TB is the path P (x, β). For odd i, Bi is a new outer blossom of
T . Perform add leaf (β(Bi ), v) for every vertex v ∈ Bi − V (T ). Merge the vertices of Bi .
For correctness note that for even i, Bi is a new inner blossom of T . Equation (2.1) gives the
subpaths of P (x, β) through the Bi . T contains the path P (xi , β(Bi )), and xi−1 is the parent of
xi . So TBi satisfies Definition 3.1 as required.
This completes the algorithm to maintain T . It is easy to see the total time in maintaining T
is O(n), since P (x, β) paths are computed in time linear in their size.
As mentioned the correspondence between paths pT and pT allows us to track potential blossom
steps in the supporting forest. This still appears to be challenging. Our second simplification of
the problem is to assume make edge adds only back edges, i.e., edges joining a vertex to some
ancestor. Clearly a blossom step for an edge vw is equivalent to blossom steps for the two edges
va and wa, for a the nearest common ancestor of v and w in T . So we can replace vw by these two
back edges.
To accomplish this reduction we use a data structure for dynamic nearest common ancestors.
Specifically the algorithm maintains a tree subject to two operations. The tree initially consists of
a dummy root ρ, and it grows using add leaf operations. The second operation is
nca(x, y) – return the nearest common ancestor of vertices x and y.
In summary we implement Edmonds’ algorithm as follows. The search algorithm constructs
supporting trees for the trees of S using add leaf operations. (Each supporting tree is rooted at
a child of ρ.) When the search discovers an edge vw ∈ E joining two outer vertices, it performs
nca(v, w) to find the nearest common ancestor a. If a = ρ an augmenting path has been found.
Otherwise the search algorithm executes the blossom-merging operations make edge(va, t) and
make edge(wa, t) for appropriate t.
Each grow, blossom, and expand step performs all the appropriate make edges, and concludes
with a min edge operation. Assume this operation returns back edge va, corresponding to edge
vw ∈ E. Assume neither va nor wa has been previously returned. As mentioned above, the
Fibonacci heap F records edge vw as the smallest candidate for a blossom step. If vw is selected
for the next step of the search algorithm, the corresponding blossom step is performed. Also
blossom-merging merge operations are executed to form the new blossom in the supporting tree.
These operations place v and w in the same blossom of the supporting tree. So wa will never be
returned by future min edges (by definition of that operation).
Let us estimate the extra time that these operations add to a search of Edmonds’ algorithm. The
algorithm for maintaining the supporting tree T uses the incremental-tree set-merging algorithm
of Gabow and Tarjan [22] for merge operations. It maintains the partition of V (T ) into maximal
blossoms in linear time. The dynamic nca algorithm of [15, 16] uses O(n) time for n add leaf
13

operations and O(m) time for m nca operations.4 So excluding the time for make edges and
min edges the extra time is O(m + n).
We have reduced our task to solving the tree-blossom-merging problem. It is defined on a tree T
that is constructed incrementally by add leaf operations. Wlog assume the operation add leaf (x, y)
computes d(y), the depth of vertex y in its supporting tree. There are three other operations,
make edge, merge and min edge, defined as in the blossom-merging problem with the restriction
that all edges of E, i.e., the arguments to make edge, are back edges.
There is no make blossom operation – we assume Edmonds’ algorithm does the appropriate
add leaf and merge operations. Note that E is a multiset: A given edge vw may be added to E
many times (with differing costs) since although an edge uv ∈ E will become eligible for a blossom
step at most once, different u vertices can give rise to the same back edge vw. Our notation assumes
the edges of E are directed towards the root, i.e., vw ∈ E has d(v) > d(w).
As before for any vertex x, Bx denotes the blossom currently containing x. Assume that the
merges for a blossom step are performed in the natural bottom-up order, i.e., for vw ∈ E the
search algorithm traverses the path in S from Bv to Bw , repeatedly merging (the current) Bv and
its parent blossom. In tree-blossom-merging we call any set resulting from a merge operation a
“blossom” even though it need not be a blossom of Edmonds’ search algorithm.

3.1

The tree-blossom-merging algorithm

This section solves the tree-blossom-merging problem in time O(m + n log n). First it presents the
basic principles for our algorithm. Then it gives the data structure, the algorithm statement, and
its analysis.
Two features of the supporting forest are essentially irrelevant to our algorithm: The only role
played by inner vertices, prior to becoming outer, is to contribute to depths d(v). The fact that
supporting trees are constructed incrementally is of no consequence, our algorithm only “sees” new
merge and make edge operations.
Our strategy is to charge time to blossoms as their size doubles. We use a notion of “rank”
defined for edges and blossoms: The rank of an edge vw ∈ E is defined by
r(vw) = ⌊ log (d(v) − d(w))⌋.
The rank of an edge is between 0 and ⌊ log (n − 1)⌋. A blossom B has rank
r(B) = ⌊ log |B|⌋.
(Recall that in this section a blossom is a set of vertices.)
These notions are recorded in the algorithm’s data structure as follows. (A complete description
of the data structure is given below.) We use a simple representation of T , each vertex x in T
recording its parent and depth d(x). Each blossom B records its size |B| and rank r(B).
There are ≤ n merges, so each can perform a constant number of time O( log n) operations,
like Fibonacci tree delete mins or moving log n words. There are ≤ 2m make edges, so each can
perform O(1) operations. Each vertex v always belongs to some current blossom Bv , and ≤ log n
merge operations increase the rank of Bv . So we can charge O(1) time to a vertex v every time its
blossom increases in rank.
We associate each edge vw ∈ E with one of its ends, say vertex u ∈ {v, w}, in such a way that
a merge that places v and w in the same blossom increases the rank of Bu . To do this we assign a
4

After the conference version of this paper Cole and Hariharan [6] used a similar approach to allow these and
other dynamic nca operations. In addition their time bounds are worst-case rather than amortized.

14

Type
l
s
d

Conditions
r(e) > r(Av )
r(e) ≤ r(Av ), r(Av ) ≤ r(Aw )
Av 6= Aw
r(Av ) > r(Aw )

u
v
v
w

r
r(e)
max{r(Av ) + 1, r(Aw )}
r(Av )

Table 1: Edge e = vw ∈ E has Type l,s, or d defined by the Conditions. Merging blossoms Bv and
Bw gives a blossom of rank ≥ r > r(Au ) (Proposition 3.1).

r(e) > r(B)
stem(B)
l

C

s
C
r(Aw ) ≥ r(Av )
Av ⊆ B, Aw ⊆ C
B

d

D
r(Av ) > r(Aw )
Av ⊆ D, Aw ⊆ B

Figure 3: l, s, and d edges associated with blossom B, i.e., Au ⊆ B.
type to every edge – long, short or down, respectively, or synonymously l-edge, s-edge, d-edge. At
any point in the execution of the algorithm an edge has a unique type, but the type can change
over time.
Types are defined in Table 1 and illustrated in Tables 2–3 and Fig.3. In Table 1 Av and Aw
denote the blossoms containing v and w, respectively, when the definition is applied to assign the
edge’s type. Edges with a long span, type l, are treated based on their span; edges with a short
span, type s or d, are treated according to the relative sizes of the two blossoms containing their
ends. Clearly the Conditions column specifies a unique type for any edge vw with Av 6= Aw .
The edge type of e = vw determines the end that e is associated with – this is vertex u ∈ {v, w}
as specified in Table 1. As the algorithm progresses and Bv and Bw grow the type of e and other
values in Table 1 may change. (Indeed eventually we may have Bv = Bw and e has no type at
all.) The algorithm will not track every change in the type of e, instead it examines e from time
to time, each time assigning a new type according to the table. This is illustrated in Fig.3 and the
following example.
Example 1. Tables 2–3 give classifications performed in a hypothetical execution of the algorithm.
15

State
1
2
3
4

r(Av )
2
2
2
4

r(Aw )
2
4
5
6

e:r
e1 : 3
e2 : 4
e3 : 5
e1 : 6

reclassified
4
4

Table 2: s-edges e1 , e2 , e3 , all copies of vw, and their blossom parameters; u = v. e1 and e2 are
reclassified in state 4.
State
1
2
3
4

r(Av )
3
3
5
6

r(Aw )
2
2
2
3

e:r
e1 : 3
e2 : 3
e3 : 5
e1 : 6

reclassified
4
4

Table 3: d-edges e1 , e2 , e3 , all copies of vw, and their blossom parameters; u = w.
Table 2 shows type s classifications of three edges, all of which are copies of the same edge vw with
r(vw) = 2. make edge(e2 ) is executed after make edge(e1 ) and so e2 is classified after e1 , as
illustrated in states 1–2. e3 is classified later still, in state 3. At this point all three edges have
different classifications. In state 4, e1 gets reclassified (as noted in the last column of the table).
The algorithm also examines e2 , detects it as a copy of e1 with greater cost, and so permanently
discards e2 . e3 is not reclassified at this point. Further details of this scenario are given below in
Example 2. Table 3 gives a similar executions for three d-edges vw.
We call the values specified in Table 1 (specifically the edge type, blossoms Av and Aw , r, and
u) the type parameters of the classification. At a given point in the algorithm, an edge e = vw ∈ E
will have two pairs of blossoms that are of interest: the edge’s current type parameters Av and Aw ,
and the current blossoms Bv and Bw . Clearly Av ⊆ Bv and Aw ⊆ Bw .
As mentioned above a merge making Bv = Bw increases r(Bu ) to r or more. The following
proposition makes this precise.
Proposition 3.1 Let e = vw have type parameters Av , Aw , r, u.
(i) r > r(Au ).
(ii) A blossom Z containing v and w has r(Z) ≥ r.
Proof: (i) An l-edge has r = r(e) > r(Av ) and v = u. An s-edge has r ≥ r(Av ) + 1 and v = u. A
d-edge has r = r(Av ) > r(Aw ) and w = u.
(ii) Suppose e is an l-edge. Z contains the path from v to w so |Z| > d(v) − d(w) ≥ 2r(e) = 2r .
Thus r(Z) ≥ r.
If e is a d-edge then Av ⊆ Z. So r(Z) ≥ r(Av ) = r.
If e is an s-edge then Av , Aw ⊆ Z and r(Aw ) ≥ r(Av ) imply |Z| ≥ |Av |+|Aw | ≥ max{2r(Av )+1 , 2r(Aw ) }.
So r(Z) ≥ r.
✷
A crucial property for the accounting scheme is that the s and d edges are limited in number.
To make this precise recall that the vertices of a blossom form a subtree of the supporting tree, so
we can refer to a blossom’s root vertex. (This differs from the notion of base vertex. For instance
recall that a tree-merging blossom needn’t be a complete blossom of Edmonds’ algorithm.) For

16

any blossom B define stem(B) to consist of the first 2|B| ancestors of the root of B (or as many of
these ancestors that exist).
Proposition 3.2 Let e = vw where a blossom B contains v but not w and r(e) ≤ r(B). Then
w ∈ stem(B).
Remark: The proposition shows an s or d edge e = vw has w ∈ stem(Av ), since the definition of
Table 1 has r(e) ≤ r(Av ).
Proof: Let r = r(B). Thus 2r ≤ |B|. Since r(e) ≤ r, d(v) − d(w) < 2r+1 ≤ 2|B|. Rearranging to
d(v) − 2|B| < d(w) puts w in the stem of B.
✷
Let M be the set of all blossoms B formed in the algorithm that are rank-maximal, i.e., B is
not properly contained in any blossom of the same rank. A given vertex belongs to at most log n
such rank-maximal blossoms. Thus ΣB∈M |B| ≤ n log n. Our plan for achieving the desired time
bound involves using the proposition to charge each blossom B ∈ M O(1) time for each vertex in
stem(B). The total of all such charges is O(n log n) and so is within our time bound.
The data structure We describe the entire data structure as well as its motivation.
Each current blossom B has ≤ log n lists of edges designated as packet(B, r) for r ∈ [r(B) +
1.. log n]. packet(B, r) consists of edges whose classification parameters u, r have Au ⊆ B and r
matching the packet index. As motivation note all these edges are similar in the sense of producing
the same rank increase (Proposition 3.1(ii)). This allows the edges of a packet to be processed as
a single group rather than individually.5
Each packet(B, r) is implemented as a ring, i.e., a circularly linked list. This allows two packets
to be concatenated in O(1) time. A header records the packet rank r and smallest(B, r), the edge
of smallest cost in the packet.
The packets of blossom B are stored in a list in arbitrary order, i.e., they are not sorted on
r. Also if packet(B, r) currently contains no edges, its header is omitted. These two rules limit
the space for the algorithm to O(m). For graphs with m = Ω(n log n) an alternate organization is
possible: Each current blossom has an array of log n pointers to its packets.6
Each current blossom B has an additional list loose(B). It consists of all edges classified with
Au = B but not yet in a packet of B. This list is a “waiting area” for edges to be added to a
packet. It allows us to omit the array of pointers to packets mentioned above. loose(B) is a linked
list.
The value smallest(B) is maintained as the minimum cost edge in one of B’s lists (i.e., a
B-packet or loose(B)).
A Fibonacci heap H stores the values smallest(B) for every current blossom B. It is convenient
to do lazy deletions in H: An operation merge(A, B), which replaces blossoms A and B by the
combined blossom C, marks the entries for A and B in H as deleted, and inserts a new entry for
C. To do a min edge operation we perform a Fibonacci heap f ind min in H. If the minimum
corresponds to a deleted blossom, that entry is deleted (using delete min) and the procedure is
repeated. Eventually we get the smallest key for a current blossom. Its edge is returned as the
min edge value.
5

Our notion of packet is similar in spirit, but not detail, to the data structure of the same name in [18, 19].
Various devices can be added to this approach to achieve linear space for all m. Such an organization is used in
the conference version of this paper [15]. However our current approach is more uniform and simpler.
6

17

An auxiliary array I[1..n] is used to perform a gather operation, defined as follows: We have a
collection of c objects, each one having an associated index in [1..n]. We wish to gather together
all objects with the same index. We accomplish this in time O(c), by placing objects with index i
in a list associated with I[i]. An auxiliary list of indices that have a nonempty list allows the lists
to be collected when we are done, in O(c) time. Gathering operations will be done to maintain
packets in merges.
Finally each blossom B has a number of bookkeeping items: Its rank r(B) is recorded. There
is also a representation of the partition of O into blossoms. A data structure for set-merging
[36] can be used: The blossom-merging operation merge(A, B) executes a set-merging operation
union(A, B) to construct the new blossom; for any vertex v, the set-merging operation f ind(v)
gives Bv , the blossom currently containing v.
For simplicity we will omit the obvious details associated with this bookkeeping. We can also
ignore the time and space. For suppose we use a simple set-merging algorithm that does one f ind
in O(1) time, all unions in O(n log n) time, and uses O(n) space (e.g., [1]). Clearly the space and
the time for unions are within the desired bounds for Edmonds’ algorithm; the time for f inds can
be associated with other operations. Hence we shall ignore this bookkeeping.
The algorithms We present the algorithms for tree-blossom-merging, verify their correctness,
and prove the desired time bound O(m + n log n).
The algorithm maintains this invariant:
(I1)The set S of all edges in a loose-list or packet satisfies:
(i) every edge of S joins 2 distinct blossoms;
(ii) for every 2 blossoms joined by an edge of E, S contains such a joining edge of smallest
cost.
(I1) guarantees that for every blossom B, smallest(B) is a minimum-cost edge joining B to another
blossom. In proof, (ii) guarantees that such a minimum-cost edge belongs to some loose-list or
packet of B. (i) guarantees that this edge gives the value of smallest(B) (i.e., without (i) it is
possible that the minimum-cost edge has both ends in the same blossom and so is not useful).
As mentioned min edge is a Fibonacci heap find min in H. This edge gives the next blossom
step by the definition of smallest(B) and invariant (I1). The total time for all min edges is
O(n log n), since there are O(n) blossoms total and each can be deleted from H.
make edge(vw) is implemented in a lazy fashion as follows: If Bv = Bw then e is discarded.
Otherwise we classify e = vw as type l, s, or d, by computing r(e), r(Bv ) and r(Bw ), as well as
vertex u and rank r, in time O(1). e is added to loose(Bu ) and smallest(Bu ) is updated, with a
possible decrease key in H. The time is O(1) (amortized in the case of decrease key). This time
is charged to the creation of e.
We now present the algorithm for merge(X, Y ). It forms the new blossom Z. (Note that a
given edge e0 that is selected by the search algorithm for the next blossom step will cause one or
more such merge operations. The merge algorithm, and its analysis, does not refer to e0 .)
Let the set R0 consist of all edges that must be reclassified because of the merge, i.e., the edges
in packets of X or Y of rank r ≤ r(Z), and the edges in loose(X) or loose(Y ). The edges of R0
are pruned to eliminate redundancies, i.e., we ensure that at most one such edge joins Z to any
blossom B 6= Z. This is done with a gather operation using I[1..n]. Among all edges joining Z
and a given blossom B 6= Z, only one of smallest cost is retained. Edges with both ends in Z are
discarded. These actions preserve (I1).

18

Let R denote the set of remaining edges. We assign each edge of R to its appropriate packet or
loose-list, and form the final packets of Z, as follows.
Take any edge e = vw ∈ R. Compute the new type of vw using r(e), r(Bv ) and r(Bw ). Two
types of edges get added to loose-lists: An s-edge vw with w ∈ Z gets added to loose(Bv ). As usual
we also update smallest(Bv ), possibly doing decrease key. Similarly a d-edge vw with v ∈ Z gets
added to loose(Bw ).
The other edges are added to packets of Z as follows. Use the subarray I[r(Z) + 1.. log n] in a
gather operation. Specifically I[r] gathers all individual edges that are r-promoters for Z and forms
them into a list. It also gathers packet(X, r) and packet(Y, r), if they exist. These two packets are
treated as lists, not examining the individual edges, so O(1) time is spent adding them to the list
I(r). The final I(r) is taken as the list for packet(Z, r).
We complete packet(Z, r) by computing smallest(Z, r) from smallest(X, r), smallest(Y, r), and
the costs of all its other edges. The smallest of all these values gives smallest(Z). This value is
inserted into H. The loose list of Z is empty.
Example 2. The algorithm achieves the states given in Table 2 as follows.
State 1: make edge(e1 ) is executed when |Bv | = |Bw | = 4, so the algorithm adds e1 to loose(Bv ).
A merge makes |Bv | = 5 and adds e1 to packet(Bv , 3).
State 2: make edge(e2 ) is executed and merges increase |Bw | to 16. A merge makes |Bv | = 6,
transferring e2 from loose(Bv ) to packet(Bv , 4).
State 3: Achieved similar to state 2, with |Bw | increasing to 32 and then |Bv | increasing to 7.
State 4: Merges increase |Bw | to 64. A merge makes |Bv | = 16, so the edges in the rank 3 and
rank 4 packets of Bv are added to R0 . e2 is discarded by the gather operation and e3 is added to
packet(Bv , 6).
Table 3 is similar. |Bw | starts as 4 and increases to 5 (giving state 1), then 6 (state 2), then
7 (state 3). When |Bw | increases to 8 edges e1 and e2 are added to R0 , e2 is discarded and e1 is
added to the rank 6 packet (state 4).
For correctness of this algorithm observe that Proposition 3.1(i) shows the new packet assigned
to an edge of R actually exists. To show invariant (I1i) for Z consider the edges in packets of Z that
are not examined individually, i.e., edges e in a packet of X or Y of rank r > r(Z). Proposition
3.1(ii) shows a blossom containing both ends of e has rank ≥ r > r(Z). Thus e satisfies (I1i).
The time for merge is O( log n) plus O(1) for each edge added to R0 . The first term amounts
to O(n log n) for the entire algorithm (there are ≤ n merges).
We account for the second term in two ways. The first is to charge time to blossoms, via their
stems. To do this recall that an s- or d-edge vw has w ∈ stem(Bv ) (for the current blossom Bv
containing v; Proposition 3.2). We will charge the stems of blossoms B ∈ M. To do this it is
important to verify that that e is the only edge from B to w making the charge.
The second accounting mechanism is a system of credits. It pays for reclassifications that involve
loose lists. As motivation note that successive merges may move an edge e = vw from loose(Bw ) to
a packet of Bw to loose(Bv ) to a packet of Bv ; credits will pay for these moves. Define a credit to
account for O(1) units of processing time, specifically the time to process an edge e ∈ R0 . Credits
are maintained according to this invariant (I2):

19

(I2i) An l- or s-edge in a loose list has 1 credit.
(I2ii) A d-edge in a packet has 2 credits.
(I2iii) A d-edge in a loose list has 3 credits.
Lemma 3.3 The time spent on all edges of R0 in all merges is O(m + n log n).
Proof: A make edge operation adds e to the appropriate loose list with credits corresponding to
(I2i) or (I2iii). Note this accounts for the case of e starting as an l-edge.
Now consider an edge e = vw that belongs to R0 in an operation merge(X, Y ) which forms the
new blossom Z. An edge e ∈
/ R pays for the O(1) time spent processing e. This is acceptable since
no future merge has e ∈ R0 .
We can now assume e ∈ R starts as type s or d. Let e start out with classification parameters
Av , Aw , u, r. By symmetry assume X contains an end v or w of e.
If e starts out in a packet, i.e., packet(X, r), then X ∈ M. In proof, the definition of X’s
packets shows r(X) < r. Since the merge has e ∈ R, r ≤ r(Z). Combining gives r(X) < r(Z), so
X is rank-maximal.
Now consider the two possible types for e.
Case e starts as an s-edge: We consider two possibilities.
Subcase e starts in a packet: e is the unique edge of R that is directed to w. We charge the
reclassification of e to w ∈ stem(X). Clearly X ∈ M implies this is the only time the algorithm
charges w ∈ stem(X).
The charge to w ∈ stem(X) is O(1) time to account for the processing of e in this merge. In
addition if e is added to loose(Bw ) there is a charge of 3 credits which, given to e, establish (I2iii).
Subcase e starts in loose(X): (I2i) shows it has 1 credit. If e gets added to a packet the credit
pays for the processing of e. Suppose e gets added to loose(Bw ). Since e changes from s to d we
have r(Av ) ≤ r(Aw ) ≤ r(Bw ) < r(Bv ). Note Av = X, Bv = Z. (The former holds since in general,
an edge in a list loose(B) is in R0 in the first merge involving B.) So r(X) < r(Z). Thus X ∈ M.
So we can charge w ∈ Stem(X) as in the previous subcase.
Case e starts as a d-edge:
Subcase e starts in a packet: e is the only edge of R directed from Bv to w. Let A+
v be the
smallest blossom of M that contains Av . We charge the reclassification of e to w ∈ stem(A+
v ).
The reclassification has r(Z) ≥ r = r(Av ). So future blossoms Bw have r(Bw ) ≥ r(Av ), and these
+
blossoms will not have a packet of rank r(Av ) = r(A+
v ). Thus this case for w and Av will never
+
hold again. So this is the only charge the algorithm makes to w ∈ stem(Av ). (Note Av need not
be rank-maximal, we might even have Av = Bv ⊂ A+
v .)
The charge is O(1) time to account for the processing of e in this merge. In addition we charge
2 credits (1 credit) if e is added to a packet of Z (loose(Bv )) respectively.
Subcase e starts in loose(X): (I2iii) shows e has 3 credits. If e gets added to a packet 1 credit
pays for the processing and the other 2 establish (I2ii). If e gets added to loose(Bv ) we can discard
1 credit and still pay for the processing and (I2i).
✷
Example 3. In Table 3 the transfer of e1 from the rank 3 packet to rank 6 is charged to w ∈
+
stem(A+
v ). Here Av ∈ M is the rank 3 blossom corresponding to states 1 and 2. If a future merge
20

transfers e3 from the rank 5 packet to a higher one, the time is charged to w ∈ stem(A+
v ) where
+
Av ∈ M is the rank 5 blossom of state 3.
In Table 2 the transfer of e1 from the packet of rank 3 to rank 6 is charged to w ∈ stem(A+
v)
+
where Av ∈ M is the rank 2 blossom corresponding to states 1–3. This merge increases r(Bv ) from
2 to 4. If a future merge transfers e3 from the rank 5 packet to a higher one, the time is charged
+
to w ∈ stem(A+
v ) where Av ∈ M will have rank ≥ 4.
Having analyzed the algorithms for min edge, make edge, and merge, we can conclude our
tree-blossom-merging algorithm achieves the desired time bound:
Theorem 3.4 The tree-blossom-merging problem can be solved in time O(m + n log n).

4

✷

b-matching

This section presents a simple generalization of Edmonds’ algorithm to b-matching. The major
difference from ordinary matching is that b-matchings allow 2 varieties of blossoms, which we call
“light” (analogous to ordinary matching) and “heavy”. Our goal is an algorithm that is as similar
to ordinary matching as possible, by minimizing the use of heavy blossoms. Heavy blossoms seem
impossible to avoid but our algorithm keeps them “hidden”. Section 4.1 gives the basic properties
of b-matching blossoms. Section 4.2 presents the generalized algorithm and shows we can find a
maximum b-matching in time O(b(V )(m + n log n)). Section 4.4 extends the algorithm to achieve
the strongly polynomial time bound O(n log n (m+n log n)), the same bound as known for bipartite
graphs.
A degree constraint function b assigns a nonnegative integer to each vertex. We view b-matching
as being defined on a multigraph. Every edge has an unlimited number of copies. In the context
of a given b-matching, an edge of the given graph has an unlimited number of unmatched copies;
the number of matched copies is specified by the b-matching. In a partial b-matching every vertex
v has degree ≤ b(v). In a (perfect) b-matching every vertex v has degree exactly b(v). Note that
“b-matching” (unmodified) refers to a perfect b-matching, our main concern.
We use these multigraph conventions: Loops are allowed. A cycle is a connected degree 2
subgraph, be it a loop, 2 parallel edges, or an undirected graph cycle.
Contracting a subgraph does not add a loop at the contracted vertex (all internal edges including
internal loops disappear). We will even contract subgraphs that just contain a loop. We use the
following notation for contractions. Let G be a graph derived from G by contracting a number of
vertex-disjoint subgraphs. V (V ) denotes the vertex set of G (G), respectively. A vertex of G that
belongs to V (i.e., it is not in a contracted subgraph) is an atom. We identify an edge of G with
its corresponding edge in G. Thus an edge of G is denoted as xy, where x and y are V -vertices in
distinct V -vertices, and xy ∈ E. Let H be a subgraph of G. The preimage of H is a subgraph of
G consisting of the edges of H, plus the subgraphs whose contractions are vertices of H, plus the
atoms of H. V (H) (V (H)) denotes the vertex set of H (the preimage of H), respectively. Similarly
E(H) (E(H)) denotes the edge set of H (the preimage of H), respectively.

4.1

Blossoms

This section presents the basic properties of b-matching blossoms. We define blossoms in two steps,
first specifying the topology, then specializing to “mature” blossoms which can have positive dual
variables. We give a data structure for blossoms and show how blossoms are updated when the
matching gets augmented.
21

β

β

(a)

(b)

Figure 4: An augmenting trail (a) and the augmented matching (b).
Unlike ordinary matching, contracted b-matching blossoms do not behave exactly like original
vertices. For instance Fig.4(a) shows an augmenting trail – interchanging matched and unmatched
edges along this (nonsimple) trail enlarges the matching to Fig.4(b). (As in all figures square vertices
are free and heavy edges are matched. In Fig.4(b) one vertex remains free after the augment.) The
triangle is a b-matching blossom (just like ordinary matching). In Fig.4(a) contracting this blossom
gives a graph of 5 vertices that has no augmenting path. Contracted blossoms behave in a more
general way than ordinary vertices.
When a blossom becomes “mature” it behaves just like a vertex – in fact a vertex with b-value
1 just like ordinary matching! It also behaves like an ordinary matching blossom in that its z-value
can be positive (in contrast an immature blossom, e.g., the blossom of Fig.4, cannot have positive
z).
We will define a blossom in terms of its topology – it is a subgraph that when contracted can
behave like a vertex or like Fig.4. We will then specialize this notion to the case of mature blossoms.
For completeness we give 2 versions of the topological definition (Definitions 4.1 and 4.2) the second
one being more useful algorithmically. The first simpler definition is a type of ear decomposition.
Let G be a graph with a partial b-matching, i.e., every vertex v is on ≤ b(v) matched edges. A
trail is closed if it starts and ends at the same vertex. A trail is alternating if for every 2 consecutive
edges exactly one is matched. The first and last edges of a closed trail are not consecutive. Say
that the M -type of an edge is M or E − M , according to the set that contains it. The following
definition is illustrated in Fig.5.
β

β

β

x
(a)

(b)

(c)

Figure 5: Blossoms with base vertex β. (a) is light, (b) is heavy, (c) is heavy or light.
22

Definition 4.1 (Ear Blossom) A blossom is a subgraph of G recursively defined by two rules:
(a) A closed alternating trail of G is a blossom if it starts and ends with edges of the same
M -type.
(b) In a graph derived from G by contracting a blossom α, let C be a closed alternating trail
that starts and ends at α but has no other occurrence of α. The preimage of C in G is a blossom.
An example of (a) is a loop.
For uniformity we extend the notation of (b) to (a): C denotes the blossom’s trail and α denotes
its first vertex. The base vertex of a blossom is α in (a) and the base vertex of α in (b). Clearly
the base is always in V . The base vertex of blossom B is denoted β(B) (or β if B is clear). The
M -type of B is the M -type of the starting and ending edges in (a), and the M -type of α in (b). It
is convenient to call a blossom of M -type M heavy and M -type E − M light.
Example 1. In Fig.5(a) the entire graph forms a closed alternating trail that starts and ends at
β. It is a blossom with base vertex β, by part (a) of the definition. There is essentially no other
way to view the graph as a blossom, since the two edges at β do not alternate.
In Fig.5(b) the unique closed alternating trail starting and ending at β is the triangle. So it is
a minimal blossom. Contracting it to α gives a graph with a unique closed alternating trail that
starts and ends at α. So the graph is a blossom with base vertex β. Again this is essentially the
only way to parse this graph as a blossom.
Fig.5(c) is a light blossom with base β if we start the decomposition with the left triangle.
Starting with the right triangle gives a heavy blossom based at β. No other blossom decomposition
is possible.
Only light blossoms occur in ordinary matching, and they are the main type in b-matching. We
note two instances of the definition that will not be treated as blossoms in the algorithm. Both
instances are for a light blossom B. If d(β, M ) ≤ b(β) − 2 then (a) actually gives an augmenting
trail. Secondly the definition allows d(β, γ(V (B), M )) = b(β). This never holds in the algorithm –
β is either on an edge of δ(V (B), M ) or d(β, M ) < b(β).
Consider a blossom B with base vertex β. Similar to ordinary matching, each vertex v ∈ V (B)
has 2 associated vβ-trails in E(B), P0 (v, β) and P1 (v, β), with even and odd lengths respectively.
Both trails are alternating and both end with an edge whose M -type is that of B (unless the trail
has no edges). The starting edge for P1 (v, β) has the same M -type as B; it has the opposite M -type
for P0 (v, β). As examples, P1 (β, β) is the entire trail in (a). This trail could be a loop. P0 (β, β) is
always the trivial trail (β). It is the only trivial Pi trail.
The recursive definitions of the Pi trails follow easily from Definition 4.1. We omit them since
they are a special case of the Pi trails defined below.
We will use another definition of blossom that is oriented to the structures discovered in the
algorithm. We always work in graphs G where zero or more blossoms have been contracted. So a
vertex of G is an atom (defined at the start of the section) or a blossom.
Definition 4.2 (Algorithmic Blossom) Let G be a graph derived from G by contracting a family
A of zero or more vertex-disjoint blossoms. Let C be a closed trail in G that starts and ends at a
vertex α ∈ V (G). The preimage of C is a blossom B with base vertex β(B) if C has the following
properties:
If α is an atom then C starts and ends with edges of the same M -type. B has this M -type and
β(B) = α.
If α ∈ A then B has the same M -type as α and β(B) = β(α).
23

β

e

x

x

(b)

(c)

f

(a)

Figure 6: More blossom examples: (a) is a blossom with base β. Adding (b) or (c) to Fig. 5(b)
gives a larger blossom.
If v is an atom of C then every 2 consecutive edges of δ(v, C) alternate.
If v ∈ A ∩ C then d(v, C) = 2. Furthermore if v 6= α then δ(β(v), C) contains an edge of
opposite M -type from v.
As before we abbreviate β(B) to β when possible. Also B is heavy (light) if its M-type is M
(E − M ), respectively.
Example 2. The graph of Fig.5(a) can be parsed as a blossom by starting with the triangle (a light
blossom), enlarging it with the two incident edges (heavy blossom), and enlarging that with its two
incident edges (light blossom). An advantage over Definition 4.1 is that each of these blossoms is
a cycle rather than a closed trail. The algorithm will use this property.
Fig.6(a) is a blossom. It can be decomposed starting with the 5-cycle or starting with the
triangle. If we replace edge e by edge f in the matching, the triangle remains a blossom but the
overall graph does not.
Suppose the graph of Fig.5(b) is enlarged by adding the triangle of Fig.6(b) at the vertex x.
The graph is a blossom. A decomposition can start by contracting the triangle. Alternatively it
can delay the triangle contraction until the end. If we use Definition 4.1 we must delay the triangle
contraction until the end.
Suppose instead that Fig.5(b) is enlarged by adding the loop of Fig.6(c) at x. The graph
remains a blossom using Definition 4.2, since we can start by contracting the loop. This is the only
possibility – if we start by contracting Fig.5(b) as in Example 1, the loop disappears in the final
contraction, so it is not part of the blossom. So this graph is not a blossom using Definition 4.1.
When all b-values are 1 the problem is ordinary matching and it is easy to see Definition
4.2 is equivalent to ordinary matching blossoms. We will show the two definitions of blossom are
essentially equivalent. The main difference is that they need not provide the same edge sets; Fig.6(c)
gives the simplest of examples. Instead we show they provide blossoms with the same vertex sets
V (B). Strictly speaking the lemma is not needed in our development since our algorithm only uses
algorithmic blossoms.
Say two blossoms are equivalent if they have the same M-type, base vertex and vertex set (the
latter meaning V (B) = V (B ′ )). For instance the blossoms of Fig.5(b) and its enlargement with
Fig.6(c) are equivalent.
Let A∗ denote the family of blossoms involved in the recursive construction of B, i.e., A∗ consists
of A plus the A∗ family of every blossom A ∈ A. Define µ(B) = |A∗ − α∗ |, the total number of
steps in decompositions for all the blossoms of A − α. The next proof will induct on this quantity.
24

Lemma 4.1 The ear blossoms and algorithmic blossoms are equivalent families. More precisely
every ear blossom is an algorithmic blossom. Every algorithmic blossom has an equivalent ear
blossom.
Proof: Clearly we need only establish the second assertion. So consider an algorithmic blossom
B. Let A, C, and α be as in the definition. We prove that B has an equivalent ear blossom using
by induction on µ(B). The base case µ(B) = 0 corresponds directly to Definition 4.1.
Take any algorithmic blossom A ∈ A − α. Let e be an edge of δ(β(A), C) with opposite M-type
from A, let f be the other edge of δ(A, C), and let v be the end of f in V (A). (If there are two
possibilities for e choose arbitrarily.)
Case v = α(A) and e and f have the same M-type: So v = β(A). In C replace the contracted
blossom A by C(A). This gives an algorithmic blossom B1 equivalent to B. Since µ(B1 ) < µ(B)
induction shows B1 has an equivalent ear blossom. This is the desired ear blossom equivalent to B.
Case v = α(A) and e and f alternate, or {v} ⊂ α(A): In C replace A by α(A). In both cases
this gives an algorithmic blossom B1 . Since µ(B1 ) < µ(B) it has an equivalent ear blossom E1 .
Contract it to E 1 . The closed trail consisting of E 1 and C(A) is an algorithmic blossom with
µ-value < µ(B). (This motivates the definition of µ: Inducting on |A∗ | can fail here.) By induction
it has an equivalent ear blossom E2 . E2 is the desired ear blossom equivalent to B.
Case v ∈
/ α(A): Choose an occurrence of v in C(A). There is a corresponding partition of C(A)
into 2 vα(A)-trails, one starting with a matched edge, the other unmatched. Let P be the trail
whose starting edge alternates with f , and let Q be the other trail. Replacing the contraction of
A by P in C gives another alternating trail. This gives an algorithmic blossom, with an equivalent
ear blossom E1 . Contract E1 to a vertex E 1 . We will form an algorithmic blossom equivalent to
B by adding Q as follows. Let Q1 be the subtrail of Q starting with its first edge and ending with
the first edge that enters E1 . Q1 , which starts and ends with vertex E 1 , is the closed trail of an
algorithmic blossom. It has an equivalent ear blossom E2 . If V (Q − Q1 ) ⊆ V (E2 then E2 is the
desired ear blossom equivalent to B. Otherwise continue in the same manner, defining Q2 as the
subtrail of Q − Q1 starting with the first edge that leaves E2 and ending with the first edge that
enters it. Eventually Q is exhausted and we get the desired ear blossom.
✷
From now on we only use algorithmic blossoms. Our next step is to show that the Pi trails
defined above exist in these blossoms. Observe that the definition of Pi implies that for a blossom
B with edge f ∈ δ(B) and v the end of f in B, Pi (v, β(B)) alternates with f iff
(
0 f and B have the same M-type
(4.1)
i=
1 f and B have opposite M-types.
Clearly any trail Pi (v, β(B)) is required to contain at least one edge unless i = 0 and v = β(B). We
shall define P0 (β(B), β(B)) to be the trail of no edges (β(B)). (Indeed it is the only possibility for
this trail in blossoms where all edges incident to β(B) have the same M-type.) This choice satisfies
(4.1) vacuously.
We shall use the following property of the Pi trails: If f alternates with Pi (v, β(B)) as in (4.1),
and e ∈ δ(β(B)) is of opposite M-type from B, then f, Pi (v, β(B)), e is an alternating trail. This is
obvious for all cases, even when Pi (v, β(B)) has no edges.
Lemma 4.2 Trails Pi (v, β), i = 0, 1 always exist (in an algorithmic blossom).
25

Proof: The overall argument is by induction on |V (B)|. Consider two possibilities for v.
Case v is an atom: We will first specify P , the image of the desired trail Pi (v, β) in G. Then we
will enlarge P to Pi (v, β) by specifying how it traverses the various blossoms of A.
If v = α there is nothing to prove for i = 0 (P0 (v, β) = (β)). If i = 1 then P is the entire trail
C.
If v 6= α choose an arbitrary occurrence of v in C. The edges of C can be partitioned into 2
vα-trails in G, one starting with a matched edge, the other unmatched. Choose P from among
these trails so its starting edge has the M -type of the desired trail Pi (v, β).
To convert P to the desired trail, for every contracted blossom A in P we will enlarge P by
adding a trail Q that traverses V (A) correctly. To do this let e and f be the edges of P incident to
A, with e ∈ δ(β(A)) of opposite M-type from A. (If there are 2 possibilities for e choose arbitrarily.
/ α.) Let u be the end of f in V (A). Let Q be the trail
If A = α then only f exists, since v ∈
Pj (u, β(A)) of blossom A, with j chosen so the trail alternates with f at u, specifically (4.1) holds.
(For example if u = β(A) and f has M -type opposite from A then Q = P1 (β(A), β(A)).) By
definition Q alternates with e at its other end β(A). So Q (or its reverse) is the desired trail
traversing V (A). Enlarge P with every such Q. Each A occurs only once in B, so no edge is added
to P more than once, i.e., the final enlarged P is a trail.
Case v is a vertex of blossom A ∈ A: If A = α then Pi (v, β) for blossom B is that trail as defined
for blossom A.
If A 6= α we construct the desired trail as the concatenation of two trails,
(4.2)

Pi (v, β) = Pj (v, β(A))Pk (β(A), β).

Recall that a Pi trail is alternating with length congruent to i (mod 2). Apply the argument of the
previous case (v atomic) to vertex β(A), using the edge of δ(β(A), C) of opposite M-type from A
as the starting edge. We get an alternating β(A)β trail of length congruent to k (mod 2) for
(
0 A and B have the same M-type
k=
1 otherwise.
Use this trail as Pk (β(A), β) in (4.2). Define
(4.3)

j = (k + i) (mod 2).

The trail Pj (v, β(A)) exists by induction. Using it in (4.2) gives an alternating vβ-trail. (Note the
special case v = β(A), j = 0, Pj (v, β(A)) = (v).) The trail’s length is congruent to j+k ≡ i (mod 2).
Hence it qualifies as Pi (v, β).
✷
Paths Pi are not simple in general. However it is easy to see the above proof implies any trail
Pi (v, β) passes through any A ∈ A∗ at most once, and if so it traverses some trail Pj (v, β(A)),
v ∈ V (A) (possibly in the reverse direction).
The blossoms B in our algorithm have a bit more structure than Definition 4.2. (Most of the
following properties are the same as ordinary matching.) As already mentioned a light blossom will
always have d(β, γ(V (B), M )) < b(β). (In contrast a general blossom may have d(v, γ(V (B), M )) =
b(v) for every v ∈ V (B).) Furthermore C = C(B) will always be a cycle. Thus Pi -trails have a
path-like structure, more precisely: For any v ∈ V (B), Pi (v, β) ∩ C is a path in G (i.e., no repeated
vertex) with one exception: When α is atomic (so α = β), P1 (β, β) ∩ C repeats vertex β. Repeated
vertices present a difficulty for expanding a blossom – an expanded blossom must be replaced in
the search forest S by a path, not a trail. The special structure of blossoms allows this to be done,
as shown in the Section 4.2.
26

Augmenting trails
B′

B
β

v

β(B ′)

A′

A

(a)

(b)

Figure 7: Rematching a trail.
The algorithm enlarges a b-matching using a generalization of the augmenting paths of ordinary
matching. Throughout this subsection let M be a partial b-matching. An augmenting trail for M
is an alternating trail A such that M ⊕ A is a b-matching with one more edge than M . To augment
M we replace it by M ⊕ A. Our algorithm finds augmenting trails in blossoms as follows.
A vertex v ∈ V (G) is free if d(v, M ) ≤ b(v) − 1. Consider a multiset {v, v ′ } of two free vertices,
where v = v ′ only if d(v, M ) ≤ b(v) − 2. We will specify an augmenting trail with ends v and v ′ .
Start by creating an artificial vertex ε. Add an artificial matched edge from ε to each of v, v ′ . (So
v = v ′ implies the 2 matched edges are parallel.) An augmenting blossom for v, v ′ is a blossom AB
with base vertex ε; furthermore each of v, v ′ is either an atom or the base of a light blossom in
A(AB).
The corresponding augmenting trail A is P0 (v, ε) with its last edge (ε, v ′ ) deleted. Clearly A
is an alternating vv ′ -trail. The two possibilities for each end v, v ′ both ensure the first and last
edges of A are unmatched, i.e., M ⊕ A is a valid partial b-matching with greater cardinality than
M . An augment step starts with an augmenting blossom and replaces rematches the trail P0 (v, ε)
as above.
This definition allows an end v with d(v, M ) ≤ b(v) − 2 to be the base of a light blossom B. In
this case B itself gives an augmenting blossom and there is no need for a larger blossom AB. Our
algorithm will always use B, not a larger blossom.
In Fig.7 an augment rematches the trail P0 (v, β) through blossom B. Blossom A changes from
light to heavy while B remains light. The next lemma shows that in general blossoms are preserved
by the rematching of an augment step.
Lemma 4.3 Consider a graph with partial b-matching M . Let B be a blossom (not necessarily
maximal) with base vertex β. Suppose a trail Pi (v, β) through B (v ∈ V (B)) is rematched. The
new matching M ′ = M ⊕ Pi (v, β) has a blossom B ′ with the same subgraph as B and base vertex
β(B ′ ) = v. The M-type of B ′ is that of the first edge of Pi (v, β) in M ′ , unless M ′ = M .
Remarks: M ′ = M only for the trail P0 (β, β). Obviously B ′ is identical to B in this case.
Also note that the lemma implies B and B ′ have the same M-type for i = 0 (since P0 (v, β)
begins with an edge of opposite M-type from B). Similarly B and B ′ have the opposite M-types
for i = 1.
Proof: By induction assume the lemma holds for blossoms smaller than B.
27

We will use the following notation. C(B) contains its end vertex α and a vertex ζ that is either
the atom v or a blossom containing v. We will show the new blossom B ′ has α(B ′ ) = ζ. Thus α
is an interior vertex of C(B ′ ), unless ζ = α. The other vertices of C(B) remain interior vertices in
C(B ′ ).
For the main argument consider a vertex x ∈ V (G) on C(B). Assume x is on the portion of
C(B) that gets rematched else there is nothing to prove. We will show that in M ′ , x satisfies all
the relevant conditions in Definition 4.2 for B ′ as well as the relevant conditions of the lemma.
First suppose x is an atom. Consider an occurrence of x in C(B). Two edges e, f are associated
with this occurrence – e and f are either consecutive in C(B) or the two ends of C(B) when x = β.
The following two cases refer to the role x plays in this occurrence.
Case x = β:
Subcase x = v: If P0 (β, β) gets rematched then nothing changes in B. If P1 (β, β) gets rematched
then B ′ has the M-type of the rematched e and f . In both cases x = β(B ′ ) and all claims of the
lemma hold.
Subcase x 6= v: e and f have the same M-type in M . Since β = x 6= v, Pi (v, β) contains exactly
one of e, f . So these edges alternate in M ′ .
Case x 6= β: e and f alternate in M . If x 6= v then both edges are in Pi (v, β) and so they alternate
in M ′ .
The remaining case is x = v. Exactly one edge of the pair e, f is on Pi (v, β), say e. So e gets
rematched but f does not. Thus e and f have the same M-type in M ′ , x is the base of the blossom
B ′ , and its M-type is that of the rematched e.
Now assume x is a contracted blossom. The inductive assumption shows x is a blossom in M ′ ,
call it x′ .
Case x 6= ζ: Let Pi (v, β) traverse x along the trail Pj (u, β(x)). So there is an edge f ∈ C(B) ∩
Pi (v, β) ending at u, where j and f satisfy (4.1).
First suppose Pj (u, β(x)) has at least one edge of x. Its first edge e has opposite M-type from
f . The inductive assertion shows x′ has M-type that of the rematched e, which is opposite that of
the rematched f . Since f is incident to u = β(x′ ) Definition 4.2 is satisfied for x′ .
In the remaining case no edge of subgraph x is rematched, i.e., f is incident to u = β(x′ ) and
has the same M-type as x (in this case (4.1) gives the trail P0 (β(x′ ), β(x′ ))). The rematched f has
opposite M-type from x = x′ . As before Definition 4.2 is satisfied for x′ .
Case x = ζ: This implies x′ = α(B ′ ). Let e and f be the two edges of C(B) incident to x. In B ′
there is no constraint on the M-types of e and f . B ′ has the same M-type as x′ .
Suppose x contains an edge of Pi (v, β). The inductive assertion for x shows B ′ has the M-type
of the rematched first edge of Pi (v, β).
Suppose x does not contain an edge of Pi (v, β). Then v = β(x) and Pi (v, β) uses the trail
P0 (v, v) through x. If x 6= α then before rematching the first edge of Pi (v, β) has opposite M-type
from x. So after rematching this edge has the same M-type as x = x′ , as claimed in the lemma. If
x = α then no edge of B is rematched, and again the lemma holds.
✷

28

Mature blossoms
We turn to the completeness property for blossoms. Like ordinary matching the linear programming
z-values will be positive only on blossoms. However complementary slackness requires that a
blossom B with z(B) > 0 has precisely one incident matched edge,
(4.4)

b(V (B)) = 2|γ(V (B), M )| + 1.

(This principle is reviewed in Appendix B.) For B a light blossom this matched edge will be incident
to β(B). (This is required by the definition of blossom if B is not maximal. More generally as
previously mentioned our search algorithm always works with light blossoms that are either free or
have this matched edge.) A heavy blossom B may have exactly one incident matched edge, but this
is irrelevant in our algorithm. (Heavy blossoms created in a search are immediately absorbed into
a light blossom (lines 1–2 of Fig. 8 and line 5 of Fig. 9). Heavy blossoms created in an augment
as in Fig.7 are “hidden”, as shown below.) This motivates the following definition.
For any vertex v with b(v) ≥ 1 define the function bv by decreasing b(v) by 1, keeping all other
values the same. A blossom based at β is mature if γ(V (B), M ) is a bβ -matching.
Our search algorithm will extend a blossom to make it mature before any dual adjustment
makes its z-value positive (see Lemma 4.9).
Now consider the transition from one search to the next. First consider an augment step.
Blossoms with positive dual values must remain mature. This is guaranteed by the next lemma,
illustrated by B in Fig.7 assuming it is mature.
Lemma 4.4 Let B be a blossom B, not necessarily maximal. If B starts out light and mature and
gets rematched in an augmentation, it remains light and mature.
Proof: Let A be the augmenting trail and consider the trail A′ = A + (ε, v) + (ε, v ′ ). A′ contains
exactly two edges incident to B, at least one of which is incident to β(B) and matched. (If B
contains v then v = β(B), since B is mature, so (ε, v) is the claimed edge. Similarly for v ′ .) Let
f be the other edge. Since B is mature f is unmatched. Thus Lemma 4.3 shows the rematched
blossom is light and mature.
✷
Now consider the contracted graph G immediately after the matching is augmented. Some
maximal blossoms may be immature (discovery of the augmenting path prevents these blossoms
from growing to maturity). Such immature blossoms B should be discarded. (The contracted
blossom B is incident to > 1 matched edge and complicates the growth of a search tree, as discussed
in Fig.10(a) below.) To discard B, we replace its contraction in the current graph G by the atoms
and contracted blossoms of C(B) and their incident edges. So after augmenting the matching and
before proceeding to the next search, the algorithm does the following discard step:
Repeatedly discard a maximal blossom unless it is light and mature.
At the end of the discard step every maximal blossom is light and mature (and still contracted).
There can still be blossoms that are immature and/or heavy, like A and A′ in Fig.7, but they are
not maximal and so they are “hidden”, essentially irrelevant to the algorithm.

Data structure for blossoms
Blossoms are represented using a data structure similar to ordinary matching, with two new additions. First we review the previous data structure: Each maximal blossom B ∗ has a tree T (B ∗ ).
29

Every blossom B ⊆ B ∗ has an interior node in T (B ∗ ); each vertex of V (B) has a leaf. The children
of an interior node B are the nodes for the vertices of C(B) ordered as in that trail; there is only
one node for α(B), even though it occurs both first and last in the trail. The children are doubly
linked. Each link records the corresponding edge of C(B), represented by its ends in V (G). The
tree T (B ∗ ) has parent pointers.
We add two new values to facilitate construction of the Pi trails: Each blossom B records its
base vertex β(B). Also any vertex β 6= β(B ∗ ) that is the base vertex of one or more blossoms B
records an edge denoted η(B). η(B) is the edge incident to the base of B required by Definition
4.2. Specifically η(B) is the edge of δ(β, C(A)) of opposite M-type from B, for A the first ancestor
of β where β(A) 6= β. (The notation η(B) comes from our discussion of f -factors, Definition 5.1.)
As with ordinary matching this data structure has size O(|V (B ∗ )|). The proof is similar: The
leaves of T (B ∗ ) form the set V (B ∗ ). Any interior node has at least 2 children unless it is the parent
of a leaf (i.e., it represents a loop blossom). So there are ≤ 2|V (B ∗ )| interior nodes. Note that for
general blossoms B where atoms may occur multiple times in closed trails C(B) this quantity is
|V (B ∗ )| = O(b(V )). For our algorithm where atoms occur just once, |V (B ∗ )| = O(n).
The M-type of a blossom B can be determined in O(1) time: Any B with β(B) 6= β(B ∗ ) has
M-type the opposite that of η(B). More generally any B has M-type that of the two edges of
δ(β(B), B0 ), for B0 the minimal blossom containing β(B). These edges are found as the two edges
incident to the node for the parent of leaf β(B) in T (B ∗ ).
The Pi trails are computed by the algorithm for ordinary matching extended to allow two types
of trails (P0 , P1 ) and two types of blossoms (heavy and light). We will describe the extension,
relying on the original description (Section 2.1) and its notation as much as possible. The extended
routine to compute Pi (x, β(B)) uses the original 4 arguments plus the value i ∈ {0, 1}. As before
let the blossoms/atoms on the trail Pi (x, β(B)) ∩ C(B) be Bj , 0 ≤ j ≤ k. We will describe the case
r = 0 and B0 6= Bk . The other cases are similar.
As before we follow links starting at B0 to get the desired edges of C(B). The edge leaving
B0 is determined as follows: If B0 is an atom, choose it to have opposite M-type from B iff i = 0.
(Note the M-type of B is available using its base, the argument β(B).) If B0 is a blossom choose
edge η(B0 ). The last blossom/atom Bk is determined as either the blossom with base vertex β(B)
or the atom β(B).
If Bj is a blossom it engenders a recursive call (there is no such call for an atom). To specify it
let the link traversal enter Bj on the link for edge e and leave it on f (e = ∅ for j = 0, f = ∅ for
j = k). Define edges e′ , f ′ so {e′ , f ′ } = {e, f } and f ′ = η(Bj ). (For j = 0, only define f ′ = η(Bj ).
For j = k only define e′ = e.) The recursive call for Bj finds the trail Pi′ (x′ , β(Bj )) with reversal
bit r ′ , where i′ , x′ , and r ′ are determined as follows:


i
j = 0, B0 and B have the same M-type



1 − i
j = 0, B0 and B have opposite M-types
i′ =
0
e′ and Bj have the same M-type



1
e′ and Bj have opposite M-types
(
x
j=0
x′ =
′
( e ∩ V (Bj ) otherwise
r′ =

0
1

j ∈ {0, k} or f ′ = f
otherwise

As before the time for this procedure is O(|V (B)|), which we have noted is O(n) in our algorithm.
As before this bound can be improved to the output size O(|Pi (x, β(B))|) by careful path-tracing.
30

Specifically we augment the data structure so each edge η(B) has a pointer to the corresponding
link in T (B ∗ ). If x is the base vertex β(B) of one or more blossoms B the path-tracing for x starts
at the link for η(B).

4.2

b-matching algorithm

The most important differences of the b-matching algorithm from ordinary matching are that the
search forest need not alternate at outer blossoms, a blossom step may create 2 blossoms (to hide
a heavy blossom), and the Expand Step is more involved (to keep the search forest acyclic). We
begin with terminology for the algorithm.
G denotes the graph with all blossoms contracted; E denotes its edge set. S denotes the search
structure and S is that structure in G. Recall that in b-matching a vertex of V is not a blossom,
so each vertex of G is an atom or a contracted blossom but not both. The notation Bx denotes the
vertex of G containing x ∈ V ; if x is atomic then Bx = x. If d(x, M ) < b(x) then Bx is free. (If Bx
is a blossom we shall see that d(x, M ) < b(x) implies x is the base vertex of Bx .) The roots of the
forest S are the free atoms and free blossoms.
Let v be a node of S. v is inner if it is joined to its parent by an unmatched edge. Otherwise
(i.e., v is joined to its parent by a matched edge, or v is a search tree root) v is outer. We refrain
from classifying vertices contained in a blossom. (A vertex in an outer blossom can function as
both inner and outer, because of its Pi -trails.)
As before an edge is tight if it satisfies the LP complementary slackness conditions with equality
(see Appendix B). Again as before we shall see that every matched edge is tight. The following
notion identifies the edges that can be used to modify the search forest when they are tight. An
edge e = xy ∈ E − S is eligible for Bx if any of the following conditions holds:
x is an outer atom and e ∈
/ M;
Bx is an outer blossom;
Bx is an inner node and e ∈ M .
The algorithm uses the following conventions:
M denotes the current matching on G.
For any edge e, e′ denotes a new unmatched copy of e. e′ always exists in b-matching.
For related nodes x, y in S (i.e., one of x, y descends from the other) S(x, y) denotes
the S-path from x to y.
The algorithm is presented in Fig.8–9. The next three subsections clarify how it works as
follows. First we give some simple remarks. Then we state the invariants of the algorithm (which
are proved in the analysis). Lastly we give examples of the execution. These three subsections
should be regarded as commentary – the formal proof of correctness and time bound is presented
in Section 4.3.
Remarks The grow step adds only one edge, unlike ordinary matching. One reason is that an
inner vertex may have an arbitrary number of children: The possibility of > 1 child comes from an
inner atom on many matched edges. The possibility of no children arises when a new inner vertex
has all its matched edges leading to vertices that are already outer.
A second reason comes from the definition of eligibility. It allows an outer vertex to have a
child using a matched edge. So an outer vertex may have an arbitrary number of children, using
matched or unmatched edges. This also shows that the search forest need not alternate the same
way as ordinary matching.
In the blossom step the test e ∈ E is equivalent to the condition Bx 6= By or Bx = By is atomic.
The second alternative allows a blossom whose circuit is a loop. This can occur for an atom that
31

1

2

3

make every free atom or blossom an (outer) root of S
loop
if ∃ tight edge e = xy ∈ E eligible for Bx with y ∈
/ S then
/* grow step */
add e, By to S
else if ∃ tight edge e = xy ∈ E, eligible for both Bx and By then
/* blossom step */
if Bx and By are in different search trees then
/* e plus the S-paths to Bx and By give an augmenting blossom B */
augment M using B, and end the search
α ← the nca of Bx and By in S
C ← the cycle S(α, Bx ), e, S(By , α)
if α is an inner node of S then /* α is atomic */
contract C to a heavy blossom /* C is the new Bx */
f ← the unmatched edge of S incident to α
α ← the outer node of S on f
C ← the closed cycle f, Bx , f ′
if α is atomic and d(α, M ) ≤ b(α) − 2 then /* α is a search tree root */
augment M using blossom C, and end the search
contract C to an outer blossom /* C is the new Bx */
else if ∃ inner blossom B with z(B) = 0 /* B is mature */ then
/* expand step */
define edges e ∈ δ(B, S − M ), f ∈ δ(B, M ) /* f needn’t be in S */
let P0 be the trail e, P0 (v, β(B)), f , where v = e ∩ V (B), β(B) = f ∩ V (B)
remove B from S /* S is now invalid */
Expand (B, e, f ) /* enlarge S by a path through B to f */
else adjust duals
Figure 8: Pseudocode for a b-matching search.

32

Procedure Expand(B, e, f )
/* B: a blossom formed in a previous search, or an atom.
B is a mature blossom in the initial invocation
but may later be immature
e: edge entering B, already in S
f : edge leaving B
β: base vertex of B if B is a blossom

4

5

6

7

Expand enlarges S by adding a path of edges of B that joins e to f
*/
if B a blossom with z(B) > 0 or B an atom /* e & f alternate */ then
make B a node of S
else if B light and e ∈ δ(β, M ) /* e.g., B light and P0 contains P1 (β, β) */ then
make B an outer node of S
else if e, f ∈ δ(β, E − M ) then
/* B is heavy and P0 contains trail P1 (β, β) */
let e = uβ
let C be the length 2 cycle Bu , e, B, e′ , Bu
if d(u, M ) ≤ b(u) − 2 /* u is a search tree root */ then
augment M along C and end the search
let B ′ be the blossom defined by C(B ′ ) = C
replace e in S by outer node B ′
else
let P = (e1 , B1 , e2 , B2 , . . . , ek , Bk , ek+1 ) be the trail E(P0 ) ∩ (C(B) ∪ {e, f })
/* e1 = e, ek+1 = f, Bi a contracted blossom or an atom
P is a path
*/
for i = 1 to k do
if i > 1 then add ei to S; Expand (Bi , ei , ei+1 )
for every blossom B ′ of C(B) − P do
repeatedly discard a maximal blossom in V (B ′ ) unless it is light and mature
Figure 9: Expand(B, e, f ) for b-matching blossoms B.

33

is either inner with a matched loop or outer with a tight loop. (Loop blossoms do not occur for
blossoms Bx since our contraction operation discards loops.)
The contraction of line 3 creates an outer blossom that is light. When a heavy blossom is
created in line 2 it gets absorbed in the light blossom of line 3. We shall see this is the only way a
heavy blossom occurs in the search algorithm.
In the expand step note that edge f may or may not be in S (as mentioned above for the
grow step). This motivates the structure of Expand(B, e, f ), which assumes on entry that e is an
edge of S but makes no assumption on f . Also the trail P0 is used for succinctness. An efficient
implementation is described in the last subsection of Section 4.3.
If the duals are adjusted (last line of Fig.8) our assumption that the graph has a (perfect)
b-matching guarantees the new duals allow further progress (i.e., a grow, blossom, or expand step
can be done; this is proved in Lemma 4.11 and the discussion following it).
A tight edge xy with Bx ∈ S is ignored by the algorithm in 2 cases: Bx an outer atom with
xy ∈ M , and Bx inner with xy ∈
/ M.
In procedure Expand the last case (starting at line 7) corresponds roughly to the expand step
for ordinary matching. The purpose of the preceding cases is to eliminate repeated vertices in P0 ,
which of course cannot be added to the search forest S.
Invariants The first several invariants describe the topology of S. As before say that S alternates
at an S-node v if any edge to a child of v has opposite M -type from the edge to the parent of v;
if v is a root then any edge to a child is unmatched. We can treat a root v as in the general case
by using an artificial vertex AV as its parent (as done for augmenting trails): AV has an artificial
matched edge to each atomic root as well as the base vertex of each blossom root.
(I1)

S alternates at any node that is not an outer blossom.

(I2)

Let B be a maximal blossom with base vertex β. B is light.
If B is inner or not in S then it is mature, and β is on a matched edge incident to B.

If B is outer then every vertex x ∈ V (B) has d(x, M ) = b(x) unless B is a root of S,
x = β, and d(x, M ) = b(x) − 1. If B is a nonroot of S then β is on the matched edge leading to
the parent of B.
(I3)

For every blossom B (maximal or not) C(B) is a cycle.

In detail (I1) means the following: Any child of an inner S-node is outer. Any child of an outer
atom is inner (this includes the case of an atomic search tree root). A child of an outer blossom
may be outer or inner. Note that the first of these properties implies the parent of an inner node
is outer. Equivalently, S alternates at both ends of an unmatched edge in S.
Note that (I2) holds for a blossom that is maximal at any point in time.
The remaining invariants deal with the dual variables. (The duals for b-matching are reviewed
in Appendix B.)
(I4)
An edge is tight if it is matched, or it is an edge of S, or it is an edge of a contracted
blossom.
(I5)

A blossom with z(B) > 0 is light and mature.

Note that in (I5) blossom B need not be maximal.
34

v

v
e

v

f g
e

f

x

h

e
(a)

v

(b)
v

f

f’

e

f’

f

f’

w

e

y
e

e

(d)

w

A

f

(c)

B1

d
x

e

e
e2

B2

e2

(f)

(g)

(h)

B2
f

f
(e)

B’

B

B1

(i)

Figure 10: Algorithm examples.
Examples Grow Step: In Fig.10(a) the triangular blossom Bx is inner. Its incident matched edge
e leads to a node that is already outer. So unlike ordinary matching Bx has no corresponding grow
step. Bx also illustrates the possibility of an expand step where the inner blossom is a leaf (unlike
ordinary matching).
(I2) requires the inner blossom Bx to be mature. Suppose it was immature. A matched edge
like f incident to Bx might exist. A grow step for f would be invalid, since S does not contain
an alternating trail from f to a free vertex. Requiring inner blossoms to be mature avoids this
complication.
Blossom Step: In Fig.10(b) v is an outer vertex. An atomic v is the root of the alternating subtree
of edges e, f, g, h. If v is a blossom a blossom step can be done for the matched copy of e, as well
as the matched copy of g. The unmatched copy of h is necessarily tight so a blossom step can be
done for it. These blossom steps illustrate how outer blossoms can be enlarged to become mature.
(Edge e of Fig.10(g) illustrates another case.)
In Fig.10(c) the unmatched loop e may not be tight. If it becomes tight it forms an augmenting
blossom if the free vertex v lacks at least 2 matched edges. The algorithm can repeatedly match
copies of e as long as this condition holds. If eventually v lacks 1 matched edge another copy of e
forms a light blossom.
Fig.10(d) shows a search tree when a blossom step for e is discovered. The triangle is made
a heavy blossom. If v lacks at least two edges the matching is augmented as in Fig.10(e). The
discard step then abandons the triangle blossom. (Edges f, f ′ show the blossom is immature.) If v
lacks only one edge the light blossom A of Fig.10(f) is formed. This illustrates that the algorithm
never creates heavy blossoms that are maximal.
In Fig.10(g) a blossom step creates the loop blossom Bx . Edge e is a matched copy of the search
tree edge d. A blossom step may be done for e, Bx and y. (y is necessarily an atom because of
d, e.) The unmatched edges f, f ′ give an augmenting trail or blossom as in Fig.10(e)–(f).
Expand Step: In Fig.10(h) blossom B is inner and mature. (As an example of how this occurs,
blossom B and atom B2 may be, respectively, blossom A of Fig.10(f) and its base vertex v. In
Fig.10(f) blossom A gets positive z when duals are adjusted. An augment is done using an un35

matched edge of δ(v) ∩ δ(A), so A does not change. v is no longer free. A then becomes inner in
a grow step from the free vertex w of Fig.10(h).) A dual adjustment makes z(B) = 0 and B is
expanded. Line 7 generates two recursive calls, with arguments e, B1 , e2 and e2 , B2 , f . The first
recursive call either augments the matching as in Fig.10(e) or forms a blossom as in Fig.10(f). In
the second case Fig.10(i) gives the result of the entire expand step.
Finally suppose in Fig.10(h) blossom B is not maximal: It is included in a blossom B3 where
α(B3 ) = B, C(B3 ) is a length 2 closed trail containing B and an atom x, with 2 copies of edge
vx, say h and i where h ∈ M , i ∈
/ M . The initial call to Expand issues one recursive call with
arguments e, B, f . The rest of the expand step is as before. It results in Fig.10(i) with x no longer
in a blossom. A grow step for x is now possible using the matched edge h. Such grow steps –
involving vertices contained in a blossom that has been expanded – are not possible in ordinary
matching. They motivate the structure of the grow step in Fig.8.

4.3

Analysis

The analysis is presented in three subsections. First we prove the invariants. Then we prove the
algorithm is correct, adding some details about initialization and termination. Lastly we prove the
desired time bound, adding some implementation details for dual variables.

Proof of invariants
We show that all the invariants are preserved by every step of the algorithm. The first four lemmas
treat grow steps, blossom steps, augment steps, and expand steps, respectively. (The lemmas for the
blossom step and the expand step assume any augment is done correctly; the augment step lemma
treats the detailed augment and discard steps of Section 4.1.) Then we check dual adjustment.
Many details are straightforward so we discuss just the most interesting and representative cases.
Lemma 4.5 The grow step preserves all the invariants.
Proof: We will verify the case e ∈ M and By a blossom.
By starts out not in S, so (I2) shows it is mature and β is on its unique incident matched
edge. Thus (I2) holds when By becomes an outer blossom. (I4) shows e is tight, so adding it to S
preserves (I4). (I3) and (I5) are unchanged.
✷
Lemma 4.6 The blossom step preserves all the invariants.
Proof: We will verify the case of a blossom step that starts by making α in line 1 an outer node.
Line 3 makes C an outer blossom. (The other cases are similar to this one.)
(I1) clearly holds trivially, as do (I4) and (I5). We check (I2), (I3), and the fact that C is a
valid outer blossom, as follows:
(I3): C is the fundamental cycle of e in the forest S.
(I2): We check (I2) for the outer blossom C.
Case α is an atom: This makes α the base vertex β of the blossom C. To show C is light observe
that at least one of the two edges of δ(α, C) goes to a child of α. (I1) shows the edges at α alternate,
so that edge is unmatched. Thus C is light.
36

Since α is outer, so is C. The test preceding line 3 ensures d(x, M ) ≥ b(x) − 1 for x = α = β;
d(x, M ) = b(x) for the remaining vertices of V (C) since no atom or blossom of C − α is free. If α
is a root of S clearly it has d(x, M ) = b(x) − 1. If α is not a root it gives the desired matched edge
to the parent of C.
Case α is a blossom: (I2) shows α is light, so C is light. The other properties follow the atomic
case.
C satisfies Definition 4.2 of a blossom: Note that α and C of the definition are the same as α and
C of the algorithm. The conditions to verify are for the 3 types of vertices v of cycle C:
Case v is an atom and v = α: An edge e ∈ δ(α, C) either goes to a child of α or e is the blossom
edge joining Bx and By . In both cases e is eligible for the outer atom α, so e ∈
/ M . Thus the first
and last edges of C have the same M-type.
Case v is an atom, v 6= α: If v ∈
/ {Bx , By } then (I1) shows the 2 edges of δ(v, C) alternate. If
v ∈ {Bx , By } then one edge of δ(v, C) goes to its parent and the other is eligible for v. The two
cases of eligiblity for an atom show the edges of δ(v, C) alternate.
Case v is a contracted blossom: C is a cycle so d(v, C) = 2. The rest of the verification concerns
the case v 6= α. Let β be the base vertex of v. (I2) shows v is light, so we must show β is on a
matched edge of C. If v is outer (I2) shows the matched edge f going to v’s parent is incident to
β. Furthermore f ∈ C.
If v is inner first assume v ∈
/ {Bx , By }. (I2) implies β is on a matched edge f going to v’s
unique child, and f ∈ C. Now suppose v ∈ {Bx , By }. Edge e of the blossom step is eligible for v, so
by definition e ∈ M . (I2) shows e is incident to β, so e is the desired matched edge for blossom v. ✷
In the next two lemmas some invariants are explicitly violated during the execution of a step.
However we only require that all the invariants are satisfied at the end of the step, assuming they
hold at the start of the step.
Lemma 4.7 The augment and discard steps preserve all the invariants.
Proof: Consider the rematching of the augment step. It preserves (I5) by Lemma 4.4. (I4) holds
since the rematching is done along the trail P0 (v, ǫ) of the augmenting blossom. (I3) is unchanged.
(I1) becomes irrelevant after the rematching, since S is empty for the next search.
The rematching can violate (I2), since a maximal blossom that is incident to 2 matched edges
on the augmenting trail becomes heavy. But this violation is only temporary since the discard step
eliminates any maximal blossom that is not light and mature. Thus (I2) holds at the start of the
next search. The discard preserves (I4), since (I5) shows no blossom with positive z is eliminated,
and thus the set of tight edges does not change.
✷
We turn to the expand step of Fig.8. Let Expand(B, ė, f˙) denote the call made in the expand
step. Recall that S is defined as a forest rooted at the free atoms and blossoms. When the expand
step removes B from S, this definition and (I1) will be violated if S has a nonempty subtree
descending from f˙. (Unlike ordinary matching this subtree needn’t exist, e.g., Fig.10(a).)
To remedy this we modify (I1) to a condition (I1′ ) defined as follows. Define P to be the set
of edges of the trail P0 (defined in the expand step) that have been added to S so far. Say that a
trail in S has permissible alternation if it alternates at any node that is not an outer blossom.
37

(I1′ )
If on entry to Expand(B, e, f ) P is a trail that has permissible alternation and has e as its
last edge, then on exit P + f has permissible alternation and has f as its last edge.
Note that in general the exit trail P is an extension of the entry trail. The exit condition does not
mean that f belongs to P.
Call Expand(B, e, f ) a base case execution if it executes line 4, 5, or 6 without recursing in line
7.
Claim: If (I1′ ) holds for every base case execution of Expand then the expand step ends with P
having permissible alternation and joining ė to the end of f˙ in V (B).
Remark: Note that if f˙ was an edge of S at the start of the expand step, the claim implies f˙ and
its descendants are once again connected to a root of S.
Proof: Suppose Expand(B, e, f ) is a base case execution and Expand(B, e′ , f ′ ) is the next base case
execution. Observe that when Expand(B, e′ , f ′ ) is entered f is the last edge added to S and e′ = f .
This observation follows by a simple induction using the structure of the recursive calls when line
7 is executed. The observation implies that if the call to Expand(B, e, f ) satisfies the exit condition
of (I1′ ) then the entry condition of (I1′ ) holds for Expand(B, e′ , f ′ ).
The initial call Expand(B, ė, f˙) starts with P = ė. So stringing together all the base case executions shows that when Expand(B, ė, f˙) exits, P + f˙ has permissible alternation and has f˙ as its
last edge. This gives the claim.
♦

Lemma 4.8 The expand step preserves all the invariants.
Proof: We examine the four possibilities for an execution of Expand, lines 4 – 7. We will show the
three base cases satisfy (I1′ ) and also preserve invariants (I2)–(I5). In the recursive case line 7 we
will verify that P is a path, i.e., no repeated vertices. This will complete the verification of (I1).
(By definition S is a forest and so it must be acyclic.)
Case line 4 is executed: First we show that e and f alternate (as in the comment). The test
guarding line 4 ensures B is atomic or mature, by (I5). Line 4 is not executed in the initial call
Expand(B, ė, f˙). So the current invocation was made from line 7, as Expand(Bi , ei , ei+1 ) for some
i ≤ k. The rest of the argument switches to this parent invocation. We must show that ei and ei+1
alternate when Bi is atomic or mature.
When i 6= 1, k, ei and ei+1 are the edges of δ(Bi , C(B)). The edges alternate for atomic Bi
by the definition of blossom. For mature Bi we use that definition and the definition of maturity.
When i is 1 or k (i.e., ei = e or ei+1 = f , or both) a similar inspection, using the definitions of P
and P0 , shows ei and ei+1 alternate.
The alternation of e and f implies (I1′ ). For (I2) a blossom B is light by (I5). The properties
of (I2) for inner and outer B follow easily. (I3)–(I5) are unchanged.
Case line 5 is executed: e ∈ M makes B outer. So (I1′ ) holds trivially for f and B. The other
invariants hold trivially.
Case line 6 is executed: It is easy to see B ′ is a valid blossom. To establish (I2) first observe that
B ′ is light: If u is atomic then e ∈
/ M makes B ′ light. If Bu is a contracted blossom it is light by
(I2). So again B ′ is light.
38

Next observe B ′ is outer: e is unmatched and in P and S when (this invocation of) Expand
starts. So Bu is outer by the permissible alternation of e. This makes B ′ outer. The other properties
of (I2) as well as (I3)–(I5) follow easily. (I1′ ) holds as in the previous case.
Case line 7 is executed: P is a path since (I3) implies the only Pi -trail that repeats a node of C(B)
is P1 (β, β). Such blossoms B are processed in line 5 or line 6 (see the comments). So the recursive
calls for line 7 keep P and S acyclic.
The discard step of this case ensures (I2). The remaining invariants hold by induction.
✷
We turn to the dual adjustment step. The following lemma and its corollary describe S when
duals are adjusted.
Lemma 4.9 When duals are adjusted, S alternates at every node and every maximal blossom is
light and mature.
Proof: S alternates at every node when every blossom is mature. This follows from (I1) plus the
observation that (I2) prohibits a mature outer blossom being joined to a child by a matched edge.
(I2) also shows that every maximal blossom is light. Thus to prove the lemma we need only show
that every maximal blossom is mature when duals are adjusted. (I2) shows this for inner and non-S
blossoms. So we need only consider outer blossoms.
Let B be an immature outer blossom. We will show that a grow or blossom step can be done
for B. This proves the lemma, since duals are adjusted only when no such step can be done.
Let β be the base vertex of B. Let f ∈ δ(β, M ) be the edge leading to the parent of B in S; f
is undefined if B is free. (I2) implies either B is free and every x ∈ V (B) has d(x, M ) = bβ (x) or
f exists and every x ∈ V (B) has d(x, M ) = b(x). In both cases, B immature implies there is an
edge e = xy ∈ δ(B, M − f ) with x ∈ V (B). Clearly e is tight.
Case By ∈
/ S: Since Bx is an outer blossom, e is eligible for Bx . Thus a grow step can be done to
add By to S.
Case By ∈ S: Suppose By is inner. Then e ∈
/ S. (e ∈ S − f makes By a child of Bx , so By is
outer.) As before e is eligible for Bx , and e ∈ M shows it is eligible for By . So a blossom step can
be done for e.
Suppose By is outer. Any matched edge is tight, so the unmatched copy e′ of e is tight. e′ ∈
/M
′
is eligible for both outer vertices Bx , By . So a blossom step can be done for e .
✷
In contrast to ordinary matching, duals may be adjusted with matched edges xy not in S but
incident to nodes of S: x and y can be atoms with x inner and y outer. This possibility is governed
by the following lemma.
Corollary 4.10 When duals are adjusted, any matched edge incident to a node of S joins an inner
node to an outer node.
Proof: Take e = xy ∈ M with Bx a node of S.
Case Bx is inner: Since no grow step can be done, y ∈ S. If e ∈ S it goes to a child of Bx , which
is outer as desired. If e ∈
/ S, since no blossom step can be done By is an outer atom, as desired.

39

Case Bx is outer: An unmatched copy e′ of e is tight and not in S. Since no grow step can be
done for e′ , y ∈ S. Since no blossom step can be done for e′ , By is inner, as claimed.
✷
Let us check that the invariants are preserved when duals are adjusted. (I1)–(I3) are unaffected
by the adjustment. For (I4)–(I5) recall the dual adjustment step (Fig.16 of Appendix B).
(I4): Edges of S remain tight when duals are adjusted, by the alternation of the lemma. Matched
edges incident to S remain tight, by the corollary. Edges in contracted blossoms remain tight by
definition of the dual adjustment. Thus (I4) is preserved.
(I5): A dual adjustment only increases the duals of maximal blossoms (that are outer). So the
lemma implies (I5) for the blossoms whose z value increases from 0 to positive.
We have shown the dual adjustment preserves all the invariants. Furthermore the dual variables
continue to be valid, i.e., they are feasible for the b-matching linear program (reviewed in Appendix
B). We have verified this for all cases except unmatched edges not in a blossom subgraph. This
case follows by exactly the same argument as ordinary matching.

Termination, correctness, and initialization
As in ordinary matching each step of the algorithm makes progress – it either finds an augmenting
path or modifies the graph in a way that the current search will not undo. (Each step creates a new
node of S. Obviously the number of new outer atoms, outer blossoms, or inner atoms is limited.
The number of new inner blossoms is also limited – a given blossom from a previous search can
become an inner blossom only once.) Thus the algorithm does not loop, it eventually halts.
Next we show the algorithm halts with a perfect matching. We prove this using the fact that
the maximum size of a b-matching is
(4.5)

min b(I) +
I⊆V

X
⌊b(C)/2⌋
C

where C ranges over all nontrivial connected components of G − I (a component is trivial if it
consists of one vertex x but no loop, i.e., xx ∈
/ E) [34, Theorem 31.1]. In fact it is straightforward
to see that the above quantity upper-bounds the size of a b-matching (a matched edge either
contains a vertex of I or has both vertices in a component C). Our derivation gives an alternate
proof that the bound is tight.
Consider a search that fails, i.e., no grow, blossom, or expand step is possible, and duals cannot
be adjusted to remedy this.
Lemma 4.11 In a failed search, any edge e ∈ E incident to an S-vertex is either spanned by a
blossom or incident to an inner atom.
Proof: A dual adjustment decreases the z-value of any inner blossom, and lowering it to 0 allows
an expand step to be done. So there are no inner blossoms.
We can assume e ∈
/ M ∪ S by using an unmatched copy. Let e = uv. If the lemma does not
hold we can assume at least one of Bu , Bv is outer, say Bu . Furthermore either Bv ∈
/ S or Bv is
outer with either Bu 6= Bv or Bu = Bv atomic (since e is not spanned by a blossom). Since no grow
or blossom step can be done, e is not tight, in each of these cases. A dual adjustment decreases
the y-value of any vertex in an outer node. So duals can be adjusted to make e tight. This makes
40

a grow or blossom step possible, contradiction.

✷

Consider a failed search. Let I be the set of inner atoms. The lemma shows that deleting I
gives a collection of connected components, each of which is either (a) an outer blossom, (b) an
outer atom that has no loop, or (c) a set of non-S vertices. (For (b) note that the existence of
a loop ensures the vertex is in a blossom, by the lemma.) Corollary 4.10 shows no matched edge
joins two vertices of I. Observe that
X
|M | = b(I) +
⌊b(C)/2⌋
C

where the sum ranges over the components of type (a) or (c). (For (a) Lemma 4.9 shows the
blossom is mature. For (c) note that the non-S-vertices are perfectly matched, i.e., each v ∈
/ S is
on b(v) matched edges leading to other non-S-vertices.) This shows the upper bound (4.5) is tight.
It also shows that our algorithm, executed on an arbitrary input graph, halts with a maximum
cardinality b-matching.
When a perfect b-matching exists our algorithm finds such a matching of maximum weight. This
follows simply from the LP formulation of maximum b-matching of Appendix B. The argument is
the same as ordinary matching, so we just summarize it as follows.
The primal LP is satisfied by any (perfect) b-matching. The dual LP requires every edge to be
dual-feasible, i.e.,
ycz(e) = y(e) + z{B : e ⊆ B} ≥ w(e).

The dual adjustment step enforces this. Complementary slackness requires tightness in the above
inequality for every e ∈ M . Complementary slackness also requires every blossom with positive
z to be mature. These two complementary slackness conditions are guaranteed by (I4) and (I5)
respectively. We conclude the final b-matching has maximum weight, and our algorithm is correct.
In fact the algorithm provides an alternate proof that the LP of Appendix B is a correct formulation
of maximum b-matching.

As in ordinary matching, the algorithm can be advantageously initialized to use any information
at hand. The initialization must specify a partial b-matching M , dual functions y, z, and a collection
of blossoms B. The requirements are that the duals must be feasible on every edge, tight on every
edge of M or a blossom subgraph, and invariants (I2), (I3) and (I5) must hold. The simplest
choice is a function y on vertices where y(e) ≥ w(e) for every edge e, z ≡ 0, B = ∅, and M a
partial b-matching consisting of tight edges. (Here and elsewhere z ≡ 0 means z is the function
that is 0 everywhere.) This initialization is used in Section 4.4. A handy special case is when
every vertex is assigned the same initial y-value. This gives the invariant that every free vertex has
the same y-value, which is the minimum y-value. Using this initialization when the input graph
does not have a perfect b-matching, our algorithm finds a maximum cardinality maximum weight
b-matching, i.e., a partial b-matching that has the greatest number of edges possible, and subject
to that constraint, has the greatest weight possible. This is shown in Appendix B, along with
other maximum weight variants. Other choices for initialization allow various forms of sensitivity
analysis to be accomplished in O(1) searches after finding a maximum b-matching (as in ordinary
matching).

Dual variables and efficiency analysis
The numerical computations of the algorithm are organized around a parameter ∆ maintained as
the total of all dual adjustment quantities δ in the current search. (δ is computed by the dual
41

adjustment algorithm of Fig.16, Appendix B.) We use ∆ as an offset to compute dual variables as
they change, and in a data structure to adjust duals and determine the next step to execute. The
details are as follows.
The data structure records values Y (v), Z(B) that are used to find the current value of any dual
y(v), z(B) (v ∈ V, B a blossom) in O(1) time. For example let v be a vertex currently in an outer
node of S, with ∆0 the smallest value of ∆ for which this is true, and y0 (v) the value of y(v) at
that point. (∆0 may be less than the value of ∆ when the current blossom Bv was formed.) Then
Y (v) = y0 (v) + ∆0 ,
y(v) = Y (v) − ∆,
since y(v) decreases by δ in every dual adjustment where it is outer. Similarly a blossom B that is
currently an outer node of S has
Z(B) = z0 (B) − 2∆0 ,
z(B) = Z(B) + 2∆,
for ∆0 the value of ∆ when B became outer and z0 (B) the value of z(B) at that point. (z0 (B) is
the value of z(B) at the start of the search if B was formed prior to that, or 0 if B was formed
in the current search.) Modulo changes of sign, similar equations are used to compute y(v) for v
currently an inner atom and z(B) for B currently a maximal inner blossom. Other y and z values
are computed as described in Appendix C.
To adjust duals and determine the next step of the algorithm to be executed we use a Fibonacci
heap F. F contains a node for each grow, blossom, and expand step that is a candidate for the
next step to execute. The key of each such node is the (future) value of ∆ when the step can be
done. Specifically when a blossom B becomes inner in a grow or expand step, a node for expanding
B is inserted in F with key equal to the current value of ∆ plus z(B)/2. (This node may get
deleted before the expansion, in a blossom step.) Theorem 3.4 provides the node of F for the next
candidate blossom step. Gabow [14] gives an algorithm for future grow steps that uses total time
O(mα(m, n)). For completeness Appendix C gives a simpler algorithm for grow steps. It uses total
time O(m + n log n) and so suffices for our purposes. The algorithm is also valid for a pointer
machine.
The algorithms of Fig.8–9 use linear time. We use the data structure for blossoms of Section
4.1. Note that in the expand step of Fig.8 P0 should not be computed:7 The path P in line 7 of
Fig.9 is easily computed without P0 by following appropriate links in the representation of C(B).
The details are as described for the procedure that computes Pi trails (given at the end of Section
4) except no recursive calls are made.
Blossom steps are implemented using the tree-blossom-merging algorithm of Section 3.1. This
algorithm is unchanged from ordinary matching, assuming the supporting forest is maintained
correctly. (A new case is that matched edges can cause blossom steps, and such edges may be
incident to inner vertices. Such blossom steps are handled seamlessly by the tree-blossom merging
algorithm. Alternatively they can be easily handled outside that algorithm, since matched edges
are always tight.)
Now consider the supporting forest. We modify Definition 3.1 of the supporting forest, which
uses the paths P (x, β) of ordinary matching for inner blossoms B. The corresponding trail for
7

The pseudocode uses P0 to facilitate specification of P . Explicitly computing P0 could lead to quadratic time
when there is a nesting of blossoms that get expanded, i.e., we have B = B0 ⊃ B1 ⊃ B2 ⊃ . . . where each Bi becomes
inner when Bi−1 gets expanded.

42

b-matching is P0 (x, β). To keep the supporting forest acyclic we modify this trail as follows. Let
P0− (x, β) be P0 (x, β) with every maximal subtrail of the form P1 (β(A), β(A)) replaced by the vertex
β(A). We modify Definition 3.1 so that inner blossoms B use P0− (x, β) as TB rather than P (x, β).
Note that an inner blossom B still has β(B) a vertex of the supporting forest. This allows a
blossom step for the matched edge incident to β(B) to be handled correctly.
The algorithm for maintaining T is essentially unchanged for grow and blossom steps. For
expand steps suppose Expand is executed for a blossom A which as above is represented only by
the vertex β(A). We cannot have z(A) > 0. (That would make A mature, by (I5). But maturity
implies a subtrail Pi (β(A), β(A)) of P0 (x, β) has i = 0, contradiction.) So line 5 or 6 is executed,
making A a new outer vertex. β(A) is already in the supporting tree, and the remaining vertices
of A are added to T using add leaf operations.
We conclude that our algorithm finds a maximum b-matching in total time O(b(V )(m+n log n)).

4.4

Strongly polynomial algorithm

The algorithm easily extends to a strongly polynomial version. We follow previous approaches that
use bipartite matching (i.e., network flow) to reduce the size of the problem solved on the given
nonbipartite graph [3, 17, 34]. The high-level algorithm is as follows:
Set b′ = 2⌊b/2⌋. Let M be a maximum cardinality maximum weight b′ -matching with corresponding optimal dual function y. Using M, y (and z ≡ 0, B = ∅) as the initial solution, execute
the b-matching algorithm of Section 4.2.
This is a straightforward combination of previous algorithms [3, 17, 34]. For completeness we
give the analysis.
Correctness of this algorithm – that an optimum M, y actually exists – may not be immediately
clear. We establish correctness below as part of the efficiency analysis.
Since we assume G has a perfect b-matching it has a partial b′ -matching with ≥ b(V2 ) − n edges.
So our b-matching algorithm performs ≤ n augmentations. Thus the time for the entire algorithm
is O(n(m + n log n)) plus the time to find M, y. We will see the latter strictly dominates the time.
We find M, y as follows. Extend the given graph G to G+ by adding a vertex s with b′ (s) = b′ (V ),
edges vs, v ∈ V of weight 0 and edge ss of weight W b′ (s) for
W = max{1, |w(e)| : e ∈ E(G)}.
It is easy to see there is a 1-1 correspondence between partial b′ -matchings of G and (perfect) b′ matchings of G+ , wherein a cardinality c partial matching corresponds to a perfect matching with
c loops ss. Furthermore a maximum cardinality maximum weight b′ -matching of G corresponds to
a maximum b′ -matching of G+ . To verify this last assertion it suffices to show any b′ -matching of
G+ with c loops ss, say Mc , weighs more than any such matching with d < c loops, say Md . This
follows since the relation b′ (s)/2 ≥ c ≥ d + 1 gives

w(Mc ) ≥ (W b′ (s) − W )c ≥ W b′ (s)d + W b′ (s) − W b′ (s)/2
= W b′ (s)d + W b′ (s)/2 > (W b′ (s) + W )d ≥ w(Md ).
We find a maximum b′ -matching of G+ by reducing to a bipartite graph BG. BG has vertex set
{v1 , v2 : v ∈ V (G+ )}, edge set {u1 v2 , u2 v1 : uv ∈ E(G+ )}, and edge weights and degree constraints
given respectively by
w(u1 v2 ) = w(u2 v1 ) = w(uv) and b′ (v1 ) = b′ (v2 ) = b′ (v)/2.
43

(Note s has even b′ value. Also a loop uu of G+ gives one edge u1 u2 in BG.) Let x be a maximum
b′ -matching on BG with optimum dual function y (we show x and y exist below). Define a b′ matching M on G+ by taking x{u1 v2 , u2 v1 } copies of each edge uv ∈ E(G+ ) (by our summing
convention this means a loop uu has x(u1 u2 ) copies). Define a dual function y by
y(v) = y{v1 , v2 }/2.

(4.6)

We will show that restricting M and y to G gives the optimum values desired for the main algorithm.
We first prove that the b′ -matching x exists, and M is a maximum b′ -matching on G+ . These
properties follow from the facts that
(a) any b′ -matching x on BG gives a b′ -matching M on G+ of the same weight;
(b) any b′ -matching M on G+ gives a b′ -matching x on BG of the same weight.
Recall that G+ has a b′ -matching. So (b) implies x exists. Also (a) is obvious from the above
construction of M on G+ . So we need only prove (b).
We prove (b) using the Euler tour technique: Let M be a b′ -matching on G+ . Since b′ is even
on G+ , the edges of M form a collection of closed trails. Traverse each trail, and for each edge
uv traversed from u to v match edge u1 v2 . This applies to loops uu too. For each vertex v, the
BG-matching has exactly b′ (v)/2 edges incident to each of v1 , v2 . Clearly we have the desired
matching on BG.
Applying complementary slackness to the definition of the dual function for bipartite b-matching
[34, Ch.21] we get that a b′ -matching x on BG and a dual function y are both optimum iff
(4.7)

y(e) ≥ w(e) for all edges e of BG, with equality when x(e) > 0.

(Recall our summing convention means that if e = uv then y(e) = y(u) + y(v).) Thus for every
edge e = uv of G+ ,
y(e) = (y(u1 ) + y(u2 ) + y(v1 ) + y(v2 ))/2 ≥ (w(u1 v2 ) + w(u2 v1 ))/2 = w(e).
Furthermore equality holds for e ∈ M . This follows because the matching x on BG has a mirror
image x′ defined by x′ (a1 b2 ) = x(b1 a2 ). Thus x(u1 v2 ) > 0 implies y(u1 v2 ) = w(e) as well as
y(v1 u2 ) = w(e). This calculation remains valid when e is a loop uu (i.e., u = v). So the functions
y, 0 are optimum duals for b′ -matching on G+ . Restricting M and y to G, and taking z ≡ 0, B = ∅,
gives permissible initial values for the b-matching algorithm of Section 4.2. (Recall the discussion
of initialization at the end of Section 4.2.) We have proved the main algorithm is correct.
We find x, y on BG using an algorithm for minimum cost network flow. Specifically the problem
on BG is a transportation problem, where x is an optimum integral solution and y is an optimum
dual function [34, Ch.21]. The optimality conditions (4.7) are precisely those for the transportation
problem (assuming the trivial sign flip to convert our maximum weight problem to a minimum cost
problem). Orlin solves the transportation problem (more generally the transhipment problem)
in time O(n log n(m + n log n)) [28]. It gives both x and y. Using this we obtain our strongly
polynomial bound:
Theorem 4.12 A maximum b-matching can be found in time O(min{b(V ), n log n}(m + n log n)).
✷

5

f -factors

The fundamental difference between f -factors and b-matching is illustrated in Fig.11, which shows
a search structure for f -factors. Recall that f -factors are defined on arbitrary multigraphs – unlike
44

η1
α1

B
B1

B3
η2

η3

α2

α3
B2
α4
α5
Figure 11: f -factor search structure. As usual dashed edges are not part of the structure; in this
figure they are αi , all matched.
b-matching, edges have a limited number of parallel copies. The parallel copies in b-matching often
allow a blossom to be enlarged using an incident matched edge and its parallel unmatched edge
(e.g., in Fig.11 blossom B and α3 ; also B3 and α2 ). The parallel unmatched edge needn’t exist for
f -factors (in fact the search structure of Fig.11 might be maximal). This in turn leads to another
major difference: the linear programming z dual variables are assigned to blossom/incident-edge-set
pairs rather than just blossoms.
The organization of the f -factor section is the same as b-matching: Section 5.1 gives the basic
properties of blossoms. Section 5.2 presents our algorithm that finds a maximum f -factor in time
O(f (V )(m + n log n)). Section 5.4 extends the algorithm to achieve the strongly polynomial time
bound O(m log n (m + n log n)), the same bound as known for bipartite graphs.
We use the same terminology as b-matchings whenever possible – we introduce each such duplicate term and point back to its complete definition in Section 4. For instance the degree constraint
function f , a partial f -factor, and all terminology regarding multigraphs and contractions are the
same as before.

5.1

Blossoms

Similar to b-matching we define immature and mature blossoms, give a data structure, and show
how blossoms are updated when the matching gets augmented.
Blossoms are defined as before by Definition 4.2. We add the notion of the “base edge” of a
blossom. It is the “exitting edge” of a blossom. (It is used implicitly for b-matchings.)
Definition 5.1 The base edge of a blossom A, denoted η(A), is either an edge of δ(β(A))∩δ(V (A))
with opposite M -type from A, or ∅. It satisfies these properties:
Blossoms with the same base vertex have the same base edge.
If β(A) is not the base of a maximal blossom, i.e., A ∈ A(B) − α(B) for some blossom B, then
η(A) is an edge of C(B).
It is easy to see this notion is well-defined. In particular in the last case the definition of blossom
45

B shows the edge of opposite M-type from A exists. Note that η(A) = ∅ only if β(A) is the base
of a maximal blossom. Using ∅ as a base edge is handy notation below, e.g., (5.1).
As before we abbreviate β(B) to β when possible, and similarly for η(B). Heavy and light
blossoms are defined as before. In Fig.11 the 2 free loop blossoms have ∅ base edges. B and B1
are light blossoms and have base edge η1 . In Fig.5(a) the triangle blossom has η arbitrarily chosen
as one of 2 matched edges incident to its base; similarly the heavy blossom has η as one of the 2
unmatched edges incident to its base.
The family of blossoms A∗ constructing B is defined as before. The trails Pi (v, β) for f -factor
blossoms are the same as before. As before any trail Pi (v, β(B)) passes through any A ∈ A∗ (B) at
most once, and if so it traverses a trail Pj (v, β(A)), v ∈ V (A) (possibly in the reverse direction).
Furthermore for such blossoms A, η(A) is an edge in Pi (v, β(B)) unless β(A) = β(B). To prove
this we can assume A is a maximal blossom with base β(A) 6= β(B). Let D be the blossom with
A ∈ A(D) (D ∈ A∗ (B) ∪ {B}). Pi (v, β(B)) traverses the blossom trail C(D) on a subtrail, denoted
P in the proof of Lemma 4.2. For blossom A on P with A 6= α(D), P either contains both edges of
δ(A, C(D)) or, when A is the first vertex of P , the edge of δ(β(A), C(D)) of opposite M-type from
A. Both alternatives have η(A) in P .

Mature blossoms
As in b-matching complementary slackness dictates the sets that may have positive dual variables, and we use this to define which blossoms are mature. Dual variables are associated with
blossom/incident-edge-set pairs (see the review in Appendix B) but the blossoms must satisfy the
following “completeness” property. A blossom B with base vertex β and base edge η is mature if
every x ∈ V (B) − β has d(x, M ) = f (x), and furthermore,
either d(β, M ) = f (β) and η is an edge, or d(β, M ) = f (β) − 1 and η = ∅.
We shall see that in contrast to b-matching the algorithm never creates immature blossoms.
Thus the f -factor algorithm does not use a discard step.

Augmenting trails
Augmenting trails, augmenting blossoms, and the augment step are defined exactly as in b-matching.
Any blossom B on the augmenting trail, maximal or not, remains a blossom after rematching.
Lemma 4.3 shows this except for exhibiting the base edges of blossoms. We define base edges for
rematched blossoms as follows.
Let AT denote the augmenting trail P0 (v, ε) − (v ′ , ε). To be consistent with Lemma 4.3 we use
primes to denote blossoms after rematching, e.g., B ′ is the rematched blossom B.
Lemma 5.1 For any mature blossom B with δ(B, AT ) 6= ∅, η(B ′ ) is the unique edge satisfying
δ(B, AT ) − η(B) = {η(B ′ )}.
Remark: The lemma applies to all blossoms of our algorithm since they are mature. The lemma
also shows that after augmenting every blossom remains mature – even a free blossom that occurs
at an end of AT .
Proof: For some x ∈ V (B) let xx′ be the edge of δ(B, AT ) − η(B). To show this edge is uniquely
defined first note the definition of AT implies d(B, AT ) is 1 or 2, so consider two cases: If d(B, AT ) =
46

2 then η(B) ∈ E(AT ), by the definition of augmenting blossom. If d(B, AT ) = 1 then B contains
a free vertex v or v ′ so η(B) = ∅, by the definition of maturity. In both cases δ(B, AT ) − η(B) has
exactly 1 edge.
Next note that AT = P0 (v, ε) − (v ′ , ε) passes through B on a trail Pj (x, β(B)) (possibly in the
reverse direction). Suppose Pj (x, β(B)) starts with an edge e. Lemma 4.3 shows β(B ′ ) = x and
the M-type of B ′ is that of the rematched e. This is the opposite of the M-type of the rematched
xx′ . So we can take η(B ′ ) = xx′ .
The remaining possibility is that Pj (x, β(B)) has no edges. So x = β(B) and B ′ = B. There
are two possibilities.
Case B is not free: xx′ alternates with η(B). So the rematched xx′ has the original M-type of
η(B). The M-type of B does not change so we can again take η(B ′ ) = xx′ .
Case B is free: B is a light blossom (even if it is not maximal, by the definition of augmenting
blossom). This makes xx′ unmatched before rematching (j = 0). So the augment makes xx′
matched and we can take η(B ′ ) = xx′ .
✷
For any mature blossom B define
I(B) = δ(B, M ) ⊕ η(B).

(5.1)

The algorithm will assign positive values to dual variables of blossom/incident-edge-set pairs of the
form B, I(B) (recall Appendix B). As an example note this is consistent with ordinary matching
and b-matching: Duals are associated with blossoms only because any blossom has I(B) = ∅. The
latter follows since η(B) is either the unique matched edge incident to B, or ∅ when this edge does
not exist.
The following lemma will be used to show that an augment step maintains validity of the dual
variables (see Lemma 5.6).
Lemma 5.2 An augment step does not change I(B) for any mature blossom B (maximal or not),
i.e, I(B) = I(B ′ ).
Proof: Let M ′ be the augmented matching M ′ = M ⊕ AT . Thus
δ(B, M ′ ) = δ(B, M ) ⊕ δ(B, AT ).
Lemma 5.1 shows
{η(B ′ )} = δ(B, AT ) ⊕ η(B).
By definition I(B ′ ) = δ(B, M ′ ) ⊕ η(B ′ ). Substituting the displayed equations transforms this to
δ(B, M ) ⊕ η(B) = I(B).
✷

Data structure for blossoms
The data structure is the one used in b-matching with one minor extension: The base edge η(B)
is stored even for maximal blossoms, if it exists. This edge is not needed in b-matching, but it is
required for f -factors. For instance it defines I(B)-sets (via (5.1)) which in turn defines the dual
variables.
47

5.2

f -factor algorithm

Compared to b-matching an f -factor algorithm has more restrictions on grow and blossom steps,
since edges have a limited number of copies. This necessitates assigning z dual variables to
blossom/incident-edge-set pairs, and introduces the case of matched edges that are not tight. It
also simplifies the algorithm by making matched and unmatched edges more symmetric. Similarly
heavy blossoms are required in both the linear programming formulation and the algorithm.
We present both the search algorithm and the dual adjustment step – the latter differs enough
from ordinary matching and b-matching to merit detailed discussion.

8

9

make every free atom or blossom an (outer) root of S
loop
/ S then
if ∃ tight edge e = xy ∈ E eligible for Bx with y ∈
/* grow step */
add e, By to S
else if ∃ tight edge e = xy ∈ E eligible for both Bx and By then
/* blossom step */
if Bx and By are in different search trees then
/* e plus the S-paths to Bx and By give an augmenting blossom B */
augment M using B and end the search
α ← the nca of Bx and By in S
C ← the cycle S(α, Bx ), e, S(By , α)
if α is atomic and d(α, M ) ≤ f (α) − 2 then /* α is a search tree root */
augment M using blossom C and end the search
contract C to an outer blossom with η(C) = τ (α) /* C is the new Bx */
else if ∃ inner blossom B with z(B) = 0 then
/* expand step */
let e = τ (B), f = η(B), v = e ∩ V (B), β(B) = f ∩ V (B)
let Ce be the subtrail of C(B) traversed by the alternating trail Pi (v, β(B)),
where i ∈ {0, 1} is chosen so Pi (v, β(B)) alternates with e at v
if Ce = C(B) then make B an outer blossom by assigning η(B) ← e
else replace B by Ce /* the blossoms of C − Ce leave S */
else adjust duals
Figure 12: Pseudocode for an f -factor search.

The search algorithm is presented in Fig.12. The definitions of the contracted graph G its edge
set E, the search structure S, its contraction S, the Bx sets denoting blossoms or atoms, and free
nodes are the same as b-matching. To define inner/outer classification let v be a node of S. If v is
not a search tree root let τ (v) be the edge to its parent.
Node v of S is outer if any of the following conditions holds:
v is a search tree root;
v is an atom with τ (v) ∈ M ;
v is a blossom with τ (v) = η(v).
Otherwise v is inner, i.e., τ (v) exists but either of the following holds:
v is an atom with τ (v) ∈
/ M;
v is a blossom with τ (v) 6= η(v).
48

In contrast with b-matching, an outer blossom can have τ (v) ∈
/ M (i.e., when it is heavy) and
an inner blossom can have τ (v) ∈ M . These possibilities are illustrated by B2 and B3 respectively
in Fig.11.
Eligibility is defined as follows. The motivation is to ensure that paths in S have the same
structure as trails in blossoms:
An edge e = xy ∈ E − S is eligible for Bx if any of the following conditions holds:
x is an outer atom and e ∈
/ M;
x is an inner atom and e ∈ M ;
Bx is an outer blossom;
Bx is an inner blossom and e = η(Bx ).
In the algorithm statement the current matching M and the paths S(x, y) are as before.
δ1 ← min{|c
y z(e) − w(e)| : e = xy ∈ E eligible for Bx with y ∈
/ S}
δ2 = min{|c
y z(e) − w(e)|/2 : e = xy ∈ E eligible for both Bx and By }
δ3 = min{z(B)/2 : B an inner blossom of S}
δ = min{δ1 , δ2 , δ3 }
for every vertex v ∈ S do
if Bv is inner then y(v) ← y(v) + δ else y(v) ← y(v) − δ
for every blossom B in S do
if B is inner then z(B) ← z(B) − 2δ else z(B) ← z(B) + 2δ
Figure 13: Dual adjustment step for f -factors.
We turn to the dual adjustment step, Fig.13. We first recall terminology explained in detail in
Appendix B. Similar to b-matching the function ycz : E → R is defined by
(5.2)

ycz(e) = y(e) + z{B : e ∈ γ(B) ∪ I(B)}.

Say edge e is dominated, tight, or underrated depending on whether ycz(e) is ≥ w(e), = w(e), or
≤ w(e), respectively; strictly dominated and strictly underrated designate the possibilities > w(e)
and < w(e) respectively. The complementary slackness conditions for optimality require e to be
dominated if it is unmatched, as in b-matching. The new requirement is that e must be underrated
if it is matched.
As usual our algorithm maintains duals to satisfy these requirements. As in b-matching there
may be strictly dominated unmatched edges; symmetrically there may be strictly underrated
matched edges. (This is expected since our algorithm has minimum cost network flow as a special
case.) The absolute values in the definitions of δ1 and δ2 reflect these possibilities, as ycz(e) − w(e)
may have arbtrary sign. The use of ycz(e) rather than y(e) (as in ordinary matching and b-matching,
Figs. 15–16) reflects the possibility that eligible edges can be in I(B) sets and so have positive z
contributions in ycz(e).
The rest of this section follows the same organization as before, giving clarifying remarks,
invariants, examples, and then the formal proof of correctness.
Remarks Many remarks for b-matching still apply, the exceptions being the simplifications in
the blossom and expand steps.

49

In the blossom step consider the cycle C, which is constructed in line 8 and then processed as
either an augmenting blossom or an outer blossom. When the augment step is executed, C is not
considered an ordinary blossom (since it is not mature). When C is processed as an outer blossom,
the definition η(C) = τ (α) assumes τ (α) = ∅ when α is the root of S.
The expand step is simpler than b-matching since all blossoms of C(B) are mature. As in
ordinary matching a new blossom in S may have z-value 0.
The algorithm maintains η values in blossom, augment and expand steps. In line 9 η-values of
blossoms in Ce are unchanged, so new blossoms of S may be inner or outer.
As before when duals are modified, our assumption that the graph has an f -factor guarantees
the new duals allow further progress (see the remark at the end of the proof of Lemma )
Invariants The definition of S alternating at node v is unchanged.
(I1)
(I2)

S alternates at any atomic node. Any root blossom is light.
Every blossom B (maximal or not) is mature.
If B is inner then it is either a leaf of S or its base edge leads to its unique child.

(I3)

For every blossom B (maximal or not) C(B) is a cycle.

(I4)
An edge is tight if it is an edge of S or an edge of a contracted blossom. Any nontight edge
is dominated if it is unmatched and underrated if matched.
v

B
B

A

τ (B)

A

τ (B)
A

η(B)

e
(a)

B

u

(b)

η(B)

v
(c)

Figure 14: f -factor algorithm examples.

Examples Strictly Underrated Edges: Fig.11 illustrates how matched edges can become underrated. Suppose a dual adjustment is done. (This requires α3 to be strictly underrated. Alternatively
we can assume α3 does not exist.) Since α5 is incident to an outer atom a dual adjustment decreases
ycz(α5 ) by δ. Since α2 is incident to an inner blossom and belongs to its I set, a dual adjustment
increases ycz(α2 ) by δ − 2δ = −δ. These adjustments exemplify the two main cases where strictly
underrated matched edges are created. (Note also that α2 or α5 may be the base edge of a blossom
not in S. So even η edges need not be tight.) The underrated edge α3 may become tight in the
dual adjustment since ycz(α3 ) increases by (−δ + 2δ) + δ = 2δ.
Eligibility: Consider Fig.11. No grow step can be done for the ineligible edge α2 . No augment step
can be done for α1 or α4 since they are ineligible at one end.

Grow Step: In Fig.11 the grow step that added the inner blossom B3 used a matched edge. This is
not possible in b-matching.
50

Blossom Step: In Fig.14(a) a blossom step can be done for e if e = η(A) = η(B) and e is tight.
Such a blossom step – for two inner vertices joined by an unmatched edge – cannot be done in
b-matching. If e 6= η(A) then a blossom step cannot be done for e. In this case e may even complete
an augmenting trail (when e is tight and d(v, M ) ≤ f (v) − 2) yet the algorithm does not augment.
The same holds if e 6= η(B), assuming B remains inner. This situation is further discussed in the
Dual Adjustment Step example below.
Augment Step: If an augment step is done for α3 in Fig.11, the edge joining blossom B3 to the free
root blossom becomes the (unmatched) base edge of both blossoms.
Expand Step: In Fig.14(b) an expand step is done for blossom B. B is made an outer node, with
base edge τ (B). So unlike b-matching an expand step may preserve B as a maximal contracted
blossom. If a similar expand step is done for B in Fig.14(c) A is made an inner blossom in S and
u and v become atoms not in S. Blossom A may not get expanded in this search even if z(A) = 0.
If it does get expanded then A becomes an outer blossom.
Dual Adjustment Step: Returning to Fig.14(a) suppose e is not the base edge of either blossom
A, B and B remains inner. A dual adjustment increases ycz(e) by δ + δ = 2δ. e becomes strictly
dominated, and the topologically valid blossom or augment step for e has been destroyed. Subsequent dual adjustments take e even further from being tight. However this cannot continue forever:
Eventually one of the inner blossoms gets expanded, and dual adjustments now increase ycz(e) by
−δ +δ = 0. When the other blossom gets expanded e becomes an unmatched edge joining two outer
blossoms/vertices. Now dual adjustments decrease the slack (c
y z(e) decreases by 2δ) and eventually
a blossom step can be done for e.

5.3

Analysis

We follow the same organization as before: The first subsection proves the invariants. The second
subsection proves correctness and adds details on initialization and termination. The last subsection
proves the desired time bound.

Proof of invariants
As before we show all the invariants are preserved by every step of the algorithm. Again our
discussion of grow, blossom, augment and expand steps just treats the most interesting cases.
Start by noting that when a search begins any free blossom is light, by (I1) from the previous
search. So (I1) is preserved when S is initialized.
Lemma 5.3 The grow step preserves all the invariants.
Proof: If Bx is inner then the definition of eligibility implies e = η(Bx ) and By will be the unique
child of Bx . So (I2) holds for Bx . (I4) continues to hold.
✷
Lemma 5.4 The blossom step preserves all the invariants.
Proof: Using the algorithm’s notation, e = xy is the edge triggering the blossom step and C is the
new outer blossom. We will verify that C satisfies Definition 4.2 as well as the definition of outer.
Furthermore since (I2) requires every blossom to be mature, we will verify the base edges satisfy
Definition 5.1. We first verify the conditions on α. There are 4 possibilities for α.
51

If α is an outer atom then (I1) shows all edges to its children are unmatched. Also if e is
incident to α then eligibility implies e is unmatched. So blossom C is light. This preserves (I1) if
α is a search tree root. If α is not a root then τ (α) is matched, so it is a valid choice for η(C).
Contracting C makes η(C) = τ (C) so C is outer.
Similarly if α is an inner atom then C is heavy, τ (α) is unmatched, and η(C) = τ (C) makes C
a valid outer blossom.
If α is an outer blossom then so is C, by definition.
Finally α cannot be an inner blossom B: η(B) is the only edge of δ(B) that can lead to a child
of B or be e (by (I2) and the definition of eligibility). So B cannot be the nca of Bx and By .
Next consider a node v 6= α that is a blossom in C. Definition 5.1 requires η(v) to be an edge
of C. If v is outer this holds since η(v) = τ (v). If v is inner then as before τ (v) and η(v) must be
the two edges of δ(v, C).
✷
Lemma 5.5 The expand step preserves all the invariants.
Proof: If Ce = C(B) then i = 1 in Pi (v, β(B)). Thus e and f are both incident to β(B) and both
have the same M-type. So changing η(B) to e preserves Definition 5.1. Since z(B) = 0 the change
also preserves ycz values.
If Ce 6= C(B) then replacing B by Ce implicitly classifies the new maximal blossoms as inner
✷
or outer, so the definition of S is maintained.
Lemma 5.6 The augment step preserves all the invariants.
Proof: Recall that an augment step is given a valid augmenting blossom – in particular a nonatomic
end v or v ′ is a light blossom by (I1). Lemma 5.2 shows no I(B) set changes in the augment. Thus
(5.2) shows every ycz(e) value remains the same and (I4) is preserved.
✷
Lemma 5.7 A dual adjustment preserves (I4) unless δ = ∞.

Proof: Any dual adjustment step has δ > 0. Let e = uv. If Bu = Bv is a blossom then clearly
ycz(e) does not change. Thus suppose e ∈ E. Assume e is not a loop – loops are covered in the
second case below, e ∈
/ S.
The quantities in ycz(e) = y(e) + z{B : e ∈ γ(B) ∪ I(B)} that may change in a dual adjustment
are limited to y(x) and z(Bx ) for x ∈ {u, v}. Clearly these quantities do not change if Bx ∈
/ S.
From now on assume x ∈ {u, v} with Bx ∈ S. Then y(x) changes by ±δ and, if Bx is a blossom,
z(Bx ) changes by ∓2δ, but this contributes to ycz(e) iff e ∈ I(Bx ). Define ∆(Bx ) to be the total
change in ycz(e) at the x end. It is easy to see that ∆(Bx ) = ±δ, more precisely,


−δ if Bx is an outer atom, or an outer blossom with e ∈
/ I(Bx ),




or an inner blossom with e ∈ I(Bx )
(5.3)
∆(Bx ) =

+δ if Bx is an inner atom, or an outer blossom with e ∈ I(Bx ),




or an inner blossom with e ∈
/ I(Bx ).
Define a sign σ by

(
+1
σ=
−1

52

e∈
/M
e ∈ M.

Case e ∈ S: We claim
(5.4)

(
+σδ
∆(Bx ) =
−σδ

e = τ (Bx )
e 6= τ (Bx ).

The claim implies ∆(Bu ) + ∆(Bv ) = 0 since one of Bu , Bv is the child of the other. Hence ycz(e)
does not change and (I4) holds.
To prove the claim consider the value of ∆(Bx ) in two symmetric cases.
Subcase ∆(Bx ) = −δ: Suppose e 6= τ (Bx ), i.e., e goes to a child of Bx . In all three cases of (5.3)
e is unmatched. Thus ∆(Bx ) = −σδ as claimed.
Suppose e = τ (Bx ), i.e., e goes to the parent of Bx . In all three cases of (5.3) e is matched.
Thus ∆(Bx ) = σδ as claimed.
Subcase ∆(Bx ) = δ: Suppose e 6= τ (Bx ). In all three cases of (5.3) e is matched. Thus ∆(Bx ) =
−σδ as claimed.
Suppose e = τ (Bx ). In all three cases of (5.3) e is unmatched. Thus ∆(Bx ) = σδ as claimed.
Case e ∈
/ S: Let Bx be a node of S. We claim
(
−σδ e eligible for Bx
(5.5)
∆(Bx ) =
+σδ e ineligible for Bx .
To prove the claim consider the value of ∆(Bx ).
Subcase ∆(Bx ) = −δ: Suppose e is eligible. In all three cases of (5.3) e is unmatched. Thus
∆(Bx ) = −σδ as claimed.
Suppose e is ineligible. This is impossible in the middle case, i.e., Bx outer with e ∈
/ I(Bx ). In
the other two cases of (5.3) e is matched. Thus ∆(Bx ) = σδ as claimed.
Subcase ∆(Bx ) = δ: Suppose e is eligible. In all three cases of (5.3) e is matched. Thus ∆(Bx ) =
−σδ as claimed.
Suppose e is ineligible. This is impossible in the middle case. In the other two cases of (5.3) e
is unmatched. Thus ∆(Bx ) = σδ as claimed.
Now we show (I4). For every edge e define
slack(e) = σ(c
y z − w(e)).
(I4) requires every edge to have nonnegative slack. A dual adjustment changes slack(e) by σ∆(Bx ).
(5.5) shows slack(e) decreases iff e is eligible for Bx .
At least one of Bu , Bv is a node of S, so assume Bu ∈ S. If Bv is also in S we can assume
∆(Bu ) = ∆(Bv ), since otherwise ycz(e) does not change and the lemma holds. So in the two cases
below, when Bv is a node of S either e is eligible for both Bu and Bv or ineligible for both.
This characterization also holds if e is a loop, i.e., u = v = x. In this case (5.5) still applies, so
∆(Bu ) = ∆(Bv ). Also the total change to ycz(e) is ∆(Bu ) + ∆(Bv ) as before, since x is an atom.
Subcase e ineligible for Bu : The dual adjustment increases the slack. Clearly (I4) continues to
hold.
53

Subcase e eligible for Bu : When the dual adjustment starts any edge has nonnegative slack, i.e.,
slack(e) = |c
y z(e) − w(e)|. If Bv ∈
/ S then initially we have |c
y z(e) − w(e)| ≥ δ1 ≥ δ. Since slack(e)
decreases by δ, slack(e) ≥ 0 after the dual adjustment and (I4) holds. Similarly if Bv ∈ S initially
slack(e) = |c
y z(e) − w(e)| ≥ 2δ2 ≥ 2δ. slack(e) decreases by 2δ so after the dual adjustment
slack(e) ≥ 0 and (I4) holds.
Remark: In this last subcase note that when δ = δ1 the corresponding minimizing edge becomes
tight. Thus a grow step can be done in the next iteration. Similarly when δ = δ2 a blossom step
has become possible. Taking δ3 into account we see that for any δ < ∞, the dual adjustment
step makes at least one grow, blossom, or expand step possible, just like ordinary matching and
b-matching.
✷
We conclude that all the invariants are preserved throughout the algorithm.

Termination, correctness, and initialization
The algorithm does not loop, by exactly the same argument as b-matching. Next we show the
algorithm halts with an f -factor, i.e., no free vertices. We shall prove this using the fact that the
maximum size of a partial f -factor is

X f (C) + |E[C, O]| 
⌋
(5.6)
min f (I) + |γ(O)| +
⌊
2
C

where the set is formed by letting I and O range over all pairs of disjoint vertex sets, and in the
summation C ranges over all connected components of G−I −O [34, Theorem 32.1]. Our derivation
gives an alternate proof of this min-max relation.
We first observe that (5.6) upper-bounds the size of any partial f -factor. In proof note that
any edge e of G satisfies exactly one of these conditions:
(i) e is incident to an I vertex;
(ii) e joins 2 O vertices;
(iii) e joins a vertex in some component C to another vertex of C or an O-vertex.
We call e type (i), (ii), or (iii) accordingly. We shall see these three types correspond respectively
to the three terms of (5.6). Note that a loop e may have any of the three types.
Clearly the number of matched edges of type (i) and (ii) is bounded by the first two terms of
(5.6) respectively. For type (iii) consider any component C. Counting edge ends shows the number
of matched edges of type (iii), |E[C, C ∪ O] ∩ M |, satisfies
X
(5.7)
2|E[C, C ∪ O] ∩ M | =
d(x, M ) − |E[C, I] ∩ M | + |E[C, O] ∩ M |.
x∈C

Obviously this implies
(5.8)

2|E[C, C ∪ O] ∩ M | ≤ f (C) + |E[C, O]|.

The third term of (5.6) follows. So (5.6) is a valid upper bound. Now we prove this bound is tight.
Consider a search that fails, i.e., no grow, blossom, or expand step can be done and the dual
adjustment step gives δ = ∞. Since δ1 = δ2 = ∞, no vertex of S has an eligible edge. Since δ3 = ∞
there are no inner blossoms.

54

In a failed search let I be the set of inner atoms and O the set of outer atoms. Deleting I ∪ O
gives a collection of connected components C. There are exactly f (I) matched edges of type (i).
This follows since an inner atom is not free, and a matched edge joining two inner atoms is eligible
(for both ends). There are exactly |γ(O)| matched edges of type (ii), since an unmatched edge
joining two outer atoms is eligible. For the type (iii) edges we will prove that any component C
has a value ∆ ∈ {0, 1} with
X
(5.9)
d(x, M ) − |E[C, I] ∩ M | + |E[C, O] ∩ M | = f (C) + |E[C, O]| − ∆.
x∈C

With (5.7) this shows the left-hand side of (5.8) is within 1 of the right. So |E[C, C ∪ O] ∩ M | =
⌊ f (C)+|E[C,O]|
⌋. This shows the number of type (iii) matched edges equals the third term of (5.6).
2
Thus (5.6) is a tight upper bound on the size of a partial f -factor.
To prove (5.9) consider 2 types of components C:
Case C ⊆ V − S: Since no vertex of C is free the first term on the left of (5.9) is f (C). Take
any e ∈ δ(C). e goes to a node v of S but e is not eligible. So v is an inner or outer atom (not a
blossom). e ∈ M iff e ∈ E[C, O]. Thus the second term on the left of (5.9) is 0 and the third term
is |E[C, O]|. So ∆ = 0 as desired.
Case C contains an S-node: We first show that C is a collection of blossoms forming a subtree of
S, with no other edges (i.e., γ(C, E) ⊆ S). Any S-node Bx of C is an outer blossom (x ∈
/ I ∪ O).
Consider an edge e = xy ∈ E with Bx a blossom of C and By a node of C. e is not eligible for Bx ,
so By is an S-node. Hence By is an outer blossom. e is not eligible for at least one of Bx , By , so e
is an edge of S, as claimed.
Let Br be the root of subtree C. Let e = rs be the edge of S from Br to its parent Bs , if such
parent exists; e = ∅ if Br is a free blossom. We claim
(5.10)

δ(C, M ) − e = E[C, O] − e.

Take any edge xy ∈ δ(C) − e, Bx ∈ C. By = y ∈ I ∪ O since C is a connected component of
G − I − O. So the claim (5.10) is equivalent to xy ∈ M iff y ∈ O. This follows from two cases: If
xy is an edge of S then y is a child of Bx . Thus xy ∈ M iff y is outer. If xy is not an edge of S
then it is not eligible for y. Again xy ∈ M iff y is outer.
Now we show (5.9) holds with ∆ = 1 in each of 3 possibilities for e.
If e = ∅ then Br contains the unique free vertex of C. Using (5.10), the 3 terms on the left of
(5.9) are f (C) − 1, 0 and |E[C, O]|.
If e is an edge then Bs = s is atomic. If s is inner then e ∈ M . Using (5.10) the 3 terms on the
left of (5.9) are f (C), 1 and |E[C, O]|. If s is outer then e ∈
/ M . Using (5.10) the terms are f (C), 0
and |E[C, O]| − 1.
We conclude the upper bound (5.6) is tight.
We have also shown that our algorithm, executed on an arbitrary input graph, halts with
a partial f -factor of maximum cardinality. In proof the analysis of a failed search shows if the
algorithm halts because δ = ∞, the current matching has size (5.6), so its cardinality is maximum.
Now we verify that our algorithm is correct, i.e., assuming an f -factor exists the algorithm finds
a maximum weight f -factor. We have just verified the algorithm’s final matching is an f -factor.
It remains to verify the LP conditions for optimality (Appendix B). (I4) gives the complementary
slackness conditions for matched and unmatched edges. We need only discuss the primal inequalities
for blossoms and the corresponding complementary slackness conditions.
55

The blossom inequalities state that every pair B, I (B ⊆ V , I ⊆ δ(B)) satisfies
(5.11)

|(γ(B) ∪ I) ∩ M | ≤ ⌊

f (B) + |I|
⌋.
2

It is easy to see this holds for any f -factor: The degree constraints imply 2|γ(B) ∩ M | + |I ∩ M | ≤
f (B) so arithmetic gives 2(|γ(B) ∩ M | + |I ∩ M |) ≤ f (B) + |I ∩ M | ≤ f (B) + |I| and integrality
gives (5.11).
Complementary slackness requires tightness in (5.11) for every blossom B and its set I(B). We
will show
(5.12)

2(|γ(B) ∩ M | + |I(B) ∩ M |) = f (B) + |I(B)| − 1.

It is easy to see that arithmetic and integrality imply this makes (5.11) tight. A light blossom B
has η(B) ∈ M − I(B), so counting degrees gives f (B) = 2|γ(B) ∩ M | + |I(B) ∩ M | + 1. Since
I(B) ∩ M = I(B) arithmetic gives (5.12). A heavy blossom B has η(B) ∈ I(B) − M , so counting
degrees gives f (B) = 2|γ(B) ∩ M | + |I(B) ∩ M |. Since I(B) ∩ M = I(B) − η(B) arithmetic gives
(5.12). We conclude the algorithm is correct.
The algorithm can be initialized with any partial f -factor F , collection of blossoms B, and dual
functions y, z that satisfies the invariants:
Every blossom is mature. Every free blossom is light.
Every blossom B has C(B) a cycle.
Every edge of a blossom subgraph is tight. Every nontight edge is dominated (underrated) if it
is unmatched (matched), respectively.
In addition z can be nonzero only on pairs (B, I(B)), B ∈ B.
As before the simplest choice is any partial f -factor, no blossoms, z ≡ 0, and a function y on
vertices with y(e) ≥ w(e) (y(e) ≤ w(e)) for every edge e that is unmatched (matched), respectively.
This and other initializations are used in Section 5.4. As with b-matching, appropriate initialization
shows that for arbitrary input graphs our algorithm finds a maximum cardinality maximum weight
f -factor, i.e., a partial f -factor that has the greatest number of edges possible, and subject to that
constraint, has the greatest weight possible. See Appendix B.

Efficiency analysis
The time to find a maximum f -factor is O(f (V )(m + n log n)). The analysis is essentially identical
to b-matching. The biggest difference is intepretation of the parameter m. In the simplest case
every copy of a fixed edge xy has the same weight. Then as in b-matching, m denotes the number
of nonparallel edges in the given multigraph G. If G has parallel edges with possibly different
weights, the same interpretation of m holds if we assume the copies of xy are given together with
their multiplicities and weights, and sorted by decreasing weight. This follows since a given search
refers to at most 2 copies of any fixed edge xy, and a new edge xy is chosen with the greatest weight
possible. If G is not given in this required form we assume a preprocessing step does the sort.
As in b-matching the algorithms of Fig. 12–13 use linear time. In the expand step Ce is easily
computed from the blossom data structure, which represents C(B) by links joining the children
of the root of T (B). For tree-blossom-merging the supporting tree T has minor changes from bmatching. In the definition, an f -factor inner blossom is traversed by a trail Pi (x, β), i ∈ {0, 1}
(i = 0 for b-matching). Analogous to b-matching we define Pi− (x, β) to be Pi (x, β) with every
56

maximal subtrail of the form P1 (β(A), β(A)) replaced by the vertex β(A). In the new Definition
3.1 an inner blossom B is represented by Pi− (x, β) in TB . (This trail may actually be the single
vertex β(B), as illustrated in Fig.14(b)–(c). In the latter note that Pi (x, β) does not pass through
u or v.)
The supporting tree is maintained similar to b-matching. A minor difference is that line 9 can
add a blossom A represented by β(A) to S. If this makes A outer the remaining vertices of A−β(A)
are added to the supporting tree. Otherwise A is inner and the supporting tree is unchanged. A
may become outer in a subsequent expand step (when z(A) = 0) or in a blossom step. In both
cases the vertices of A − β(A) are added as above.
The tree-blossom-merging algorithm is used to track blossom steps for both unmatched and
matched edges. No modifications are needed. To justify this observe that (5.5) shows once xy
becomes eligible at both ends, every dual adjustment decreases its slack by 2δ. Thus the numerical
key used in the blossom-tree merging algorithm is correct, i.e., it gives the value of total dual
adjustment when xy becomes tight.
This argument depends on the simple fact that once an edge becomes eligible it remains so.
This property was also used in ordinary matching and b-matching, but we give a formal proof for
f -factors here. Say that an edge uv is eligible at u if it is eligible for Bu . The new term avoids
referring to the time-varying Bu . This term and the next lemma come in handy in Appendix C.
Lemma 5.8 Once an edge e = uv becomes eligible at u it remains so, until it leaves E − S.
Proof: Once Bu becomes an outer node, it may get absorbed in larger blossoms but they are
always outer. So e remains eligible at u as long as it belongs to δ(Bu ) − S.
Suppose Bu transitions from being not in S to an inner node. The unique eligible edge is
uv = η(Bu ). If Bu gets expanded vertex u remains in S. Let Bu′ be the new maximal blossom
containing u, Bu′ ∈ S. We have the following possibilities.
Bu′ an outer blossom: Clearly uv is eligible for Bu′ .
Bu′ an inner blossom: uv is the base edge of Bu′ , so it remains eligible.
Bu′ an atom: The Pi trail used to expand Bu is alternating. So either u is outer and uv ∈
/ M or
u is inner and uv ∈ M . In both cases uv is eligible at u.
✷
Finally note there is nothing to verify for new nodes of S − Bu′ created in the expansion.
Theorem 5.9 A maximum f -factor can be found in time O(f (V )(m + n log n)).

5.4

✷

Related algorithms

We start by generalizing f -factors to degree-bounded subgraphs. For functions ℓ, h : V → Z+ a
subgraph H of G is an (ℓ, h)-subgraph if its degree function dH satisfies ℓ ≤ dH ≤ h.
We convert such subgraphs into f -factors as follows. Starting with the given graph G form
graph Gs by adding a vertex s, with edges vs of multiplicity h(v) − ℓ(v), v ∈ V , and the loop ss of
multiplicity ⌊h(V )/2⌋. Every new edge weighs 0. Define a degree requirement function f by
(
h(v) v ∈ V
f (v) =
h(V ) v = s.
The (ℓ, h)-subgraphs H of G correspond to the f -factors F of Gs , and corresponding subgraphs
have the same weight. In proof starting with an H, construct F by adding h(v) − dH (v) copies of
vs for every vertex v ∈ V , and |E(H)| copies of ss. This gives s degree exactly (h(V ) − 2|E(H)|) +
57

2|E(H)| = h(V ) = f (s). Obviously every v ∈ V has degree f (v), and w(H) = w(F ). Similarly
starting with an F , let H = F − s. Clearly H is an (ℓ, h)-subgraph and w(H) = w(F ).
Corollary 5.10 A maximum or minimum weight (ℓ, h)-subgraph can be found in time O(h(V )(m+
n log n)). For a minimum weight (ℓ, h)-subgraph the bound improves to O(ℓ(V )(m + n log n)) if the
weight function is nonnegative or if h ≡ dG (i.e., we seek a minimum weight ℓ-edge cover [34,
Ch.34]).
Proof: To achieve the first time bound execute the f -factor algorithm on Gs , using the given
weight function w for maximization and −w for minimization. Since f (V + s) = O(h(V )) and Gs
has O(m) distinct edges, Theorem 5.9 gives the desired bound.
Next consider minimum weight (ℓ, h)-subgraphs with nonnegative w. Use the f -factor algorithm
on Gs with weight function −w, and initial dual functions y ≡ 0 and z ≡ 0 with no blossoms. These
duals are feasible for −w. To define the initial matching let δ = ℓ(V ) mod 2. Match every copy of
every edge vs, v ∈ V , and (ℓ(V ) − δ)/2 copies of ss. To show this matching is valid first note the
degree of s in the matching is (h(V ) − ℓ(V )) + (ℓ(V ) − δ) = h(V ) − δ ≤ f (s). Also every matched
edge is tight since y ≡ 0.
The number of searches of the f -factor algorithm is (ℓ(V ) + δ)/2 = O(ℓ(V )). The time bound
for nonnegative w follows.
Finally suppose w is arbitrary but h ≡ dG . Let N = {e : w(e) < 0} and let G′ be the graph
G−N . The minimum weight (ℓ, h)-subgraph consists of N plus a minimum weight (ℓ′ , h′ )-subgraph
on G′ , where ℓ′ ≡ max{ℓ − dN , 0} and h′ ≡ dG′ . Since G′ has a nonnegative weight function the
previous case shows the time is O(ℓ(V )(m + n log n)).
✷
Next we present a strongly polynomial version of the f -factor algorithm. We use essentially
the same reduction to bipartite matching as b-matching. Assume the multigraph G is specified by
a function c : V × V → Z+ that gives the number of parallel copies of each edge. The algorithm
below rounds c up to ensure that edges do not disappear.
Define graph G′ by setting f ′ = 2⌊f /2⌋ and c′ = 2⌈c/2⌉. Let M ′ be a maximum cardinality
maximum weight f ′ -factor on G′ with corresponding optimal dual function y. For every edge e
with c′ (e) > c(e) copies of e in M ′ , remove 1 copy of e from M ′ . Let M be the resulting partial
f -factor on G. Using M, y (and z ≡ 0, B = ∅) as the initial solution, execute the f -factor algorithm
of Section 5.2 on G.
The analysis is similar to b-matching. Since we assume G has an f -factor, G′ has a partial
)
f ′ -factor with ≥ f (V
2 − n edges. At most m matched edges are deleted to form M . So our
f -factor algorithm performs ≤ m + n augmentations. Thus the time for the entire algorithm is
O(m(m + n log n)) plus the time to find M ′ , y. As before the latter strictly dominates the time.
We find M ′ , y using a graph G+ similar to b-matching: Extend graph G′ to G+ by adding a
vertex s with degree constraint
f ′ (s) = f ′ (V )
and edges vs (v ∈ V ) and ss with multiplicities and weights given respectively by
c′ (vs) = f ′ (v), c′ (ss) = f ′ (V ), w(vs) = 0, w(ss) = W f ′ (s) for W = max{1, |w(e)| : e ∈ E(G)}.
Note that f ′ and c′ remain even-valued functions. A maximum cardinality maximum weight f ′ factor of G′ corresponds to a maximum f ′ -factor of G+ . The proof is exactly the same as b-matching.
58

As before we find a maximum f ′ -factor of G+ by reducing to a bipartite graph BG. BG has vertices v1 , v2 (v ∈ V (G+ )) and edges u1 v2 , v1 u2 (uv ∈ E(G+ )) with degree constraints, multiplicities,
and edge weights given respectively by
f ′ (v1 ) = f ′ (v2 ) = f ′ (v)/2, c′ (u1 v2 ) = c′ (v1 u2 ) = c′ (uv)/2, w(u1 v2 ) = w(v1 u2 ) = w(uv).
A loop uu of G+ gives edge u1 u2 with multiplicity c′ (uu) in BG. Let x be a maximum f ′ -factor on
BG with optimum dual function y. Define an f ′ -factor M ′ on G+ by taking x{u1 v2 , u2 v1 } copies
of each edge uv ∈ E(G+ ) (by our summing convention this means x(u1 u2 ) copies of a loop uu).
x exists and M ′ is a maximum f ′ -factor on G+ , by exactly the same proof as b-matching. Define
a dual function y by y(v) = y{v1 , v2 }/2. Applying complementary slackness to the definition of
the dual function for bipartite f -factors [34, Ch.21] we get that an f ′ -factor x on BG and a dual
function y are both optimum iff for every edge e of BG,
(5.13)

x(e) = 0 =⇒ y(e) ≥ w(e); x(e) = 1 =⇒ y(e) ≤ w(e).

Now consider an edge e = uv of G+ (e may be a loop). The matching x on BG has a mirror image
defined by x′ (a1 b2 ) = x(b1 a2 ). Suppose some copy of e in BG is unmatched, say x(u1 v2 ) = 0.
(5.13) implies y(u1 v2 ) ≥ w(uv) as well as y(v1 u2 ) ≥ w(uv). Thus

y(e) = (y(u1 ) + y(u2 )) + (y(v1 ) + y(v2 )) /2 ≥ 2w(uv)/2 = w(e).

x′

Similarly if some copy of e in BG is matched then y(e) ≤ w(e). So the functions y, 0 are optimum
duals for an f ′ -factor on (the non-bipartite graph) G+ .
The matching M defined from M ′ is clearly valid on G (i.e., nonexistent matched edges are
deleted). y is also optimum on G (an unmatched edge of G is present in G+ since c′ rounds up).
We conclude that restricting M and y to G, along with z ≡ 0, B = ∅, gives permissible initial
values for our f -factor algorithm. In conclusion the main algorithm is correct.
The problem on BG is a capacitated transportation problem, where x is an optimum integral
solution and y is an optimum dual function [34, Ch.21]. We solve it using Orlin’s algorithm [28]. It
reduces the capacitated transportation problem to the uncapacitated case. The reduction modifies
the graph, but it is easy to see that the optimum dual function y on the modified graph gives an
optimum dual on the given graph. (Alternatively an optimum dual function can be found from x
itself using a shortest path computation, in time O(nm) [2].)
Orlin solves the capacitated transportation problem (more generally capacitated transhipment)
in time O(m log n(m + n log n)) [28]. It gives both x and y. Using this we obtain our strongly
polynomial bound:
Theorem 5.11 A maximum f -factor can be found in time O(min{f (V ), m log n}(m + n log n)).
✷
Next recall that for any set of vertices T of even cardinality, a T -join is a subgraph of G that has
T as its set of odd-degree vertices. For any edge cost function c it is of interest to find a minimum
cost T -join. We proceed as follows.
Let N be the set of edges of negative cost. Define t = |T |+2|N |. Let G′ be the graph G enlarged
by adding t/2 loops at every vertex, where each loop has cost 0. Define a degree-constraint function
(
t − 1 v ∈ T,
f (v) =
t
v∈
/ T.
59

A minimum cost f -factor is a minimum cost T -join augmented by enough loops to exactly satisfy the
degree constraints. In proof, let J be a minimum T -join and F a minimum f -factor. c(F ) ≥ c(J),
since F with all loops deleted gives a T -join of the same cost.
For the the opposite inequality note that wlog J consists of |T |/2 paths, each joining two vertices
of T , and ≤ |N | cycles. The latter holds since we can assume each cycle contains a negative edge.
Thus any vertex has degree d(v, J) ≤ |T | + 2|N | = t, with strict inequality if v is a terminal.
Furthermore d(v, J) and f (v) have the same parity. Hence we can add loops at each vertex to
make J an f -factor. We conclude c(J) ≥ c(F ).
For our algorithm define edge weights to be the negatives of edge costs. So we seek a maximum
weight f -factor of G′ . Initialize the algorithm with a matching M consisting of every negative
edge, and enough loops at each vertex to make f (v) ≥ d(v, M ) ≥ f (v) − 1. Furthermore y ≡ 0
and there are no blossoms. (This initialization is valid since every loop is tight and for edges of G,
every matched edge is underrated and every other edge is dominated.) Then execute the f -factor
algorithm.
The f -factor algorithm performs ≤ n/2 searches. A search uses time O(m + n log n) – although
the graph has many loops, only 2 loops at each vertex are processed in any given search. Also note
these special cases: When there are no negative edges there are |T |/2 searches. When there are no
terminals there are ≤ |N | searches.
Theorem 5.12 A minimum cost T -join can be found in time O(n(m + n log n)). If costs are
nonnegative the time is O(|T |(m+n log n)). If there are no terminals the time is O(min{|N |, n}(m+
n log n)).
We turn to the shortest path problem on a connected undirected graph G with a conservative
cost function c, i.e., negative edge costs are allowed but any cycle has nonnegative cost. We are
interested in the single source shortest path problem, i.e., given a source vertex s, we wish to find
a shortest path from each vertex v to s. We will show how the blossom tree provides a shortest
path tree that specifies all these paths. The discussion is organized into four parts as follows.
• We present a “base algorithm” that accomplishes all our goals for a subfamily of cost functions.
The goals are to show the existence of a succinct representation of all shortest paths to s, and to
give an efficient algorithm to construct the representation.
• We extend the base algorithm to show existence of the representation for arbitrary conservative
real-valued cost functions.
• For readers familiar with the generalized shortest path tree (the “gsp structure”) introduced
by Gabow and Sankowski [21], we give a simple verification that our representation is precisely
that structure.
• We extend the base algorithm to construct the representation efficiently for arbitrary conservative integral-valued cost functions. The time is O(n(m + n log n)), the best-known time bound
to find a shortest sv-path for two given vertices s, v.
We will use the f -factor algorithm to find a search structure S that handles shortest path
queries – given any vertex v, a shortest vs-path P is composed of Pi trails and can be found in time
proportional to the length of P . The base algorithm accomplishes this assuming every cycle of the
given graph has positive cost (rather than nonnegative cost). The base algorithm is as follows.
Base Algorithm. Define edge weights as the negatives of edge costs. Let G′ be the graph G with a
loop of weight 0 added at every vertex except s. Define a degree-constraint function
(
0 v = s,
f (v) =
2 v 6= s.
60

Execute the f -factor algorithm to find a maximum f -factor M and corresponding duals. Increase
f (s) to 1. Perform a search of the f -factor algorithm, initialized with M and its duals, halting
when δ = ∞. (M remains the matching but the duals and blossoms may change. Let y denote the
final dual function.)
A query algorithm outputs a shortest vs-path, for given v, as follows. The shortest distance
from v to s is d(v) = y(v) − y(s). A shortest vs-path consists of the nonloop edges in these sets:
the path P in S from Bv to Bs , plus for each blossom B in P , the path Pi (x, β(B)) with i and x
chosen as follows:
Case B = Bv : x = v and i is chosen so the first edge of Pi (v, β(Bv )) is matched.
Case B 6= Bv : Let f = xy ∈ δ(B, P ) − η(B) with x ∈ V (B). Choose i according to (4.1),
i.e., i = 0 iff f and B have the same M-type.
Now we prove the base algorithm is correct. Note that M is the set of all the loops since every
cycle of G has negative weight. The rest of the proof is in 3 claims.
Fix an arbitrary vertex v 6= s. Define the graph G′v to be G′ enlarged with a vertex v ′ that has
f (v ′ ) = 1 and a weight 0 edge vv ′ . Set y(v ′ ) = −y(v). The new graph satisfies all the invariants of
the f -factor algorithm, so we can imagine a hypothetical search of that algorithm.
Claim 1 The hypothetical search executes a blossom step for edge vv ′ and augments the matching.
Proof: vv ′ is tight and eligible for v ′ . The claim follows if vv ′ is eligible for Bv . So suppose
it is ineligible. This causes the hypothetical search to immediately halt with δ = ∞. But G′v is
connected so it has an sv-path, i.e., an f -factor, contradiction.
♦
The next claim actually holds for arbitrary augmenting paths in the f -factor algorithm, generalizing a property of Edmonds’ algorithm. For notational simplicity we only prove the special case
needed for our shortest path algorithm.
Claim 2 The augment step in the hypothetical algorithm changes the weight of the matching by
y(s) + y(v ′ ).
Proof: Every edge of the augmenting trail A is tight, by (I4). Thus the weight of the matching
changes by ycz(A − M ) − ycz(A ∩ M ). The y terms make a net contribution of y(s) + y(v ′ ), since
A alternates at every interior vertex. The z terms make no net contribution. In proof let AZ be
the set of all edges with a z(B) contribution, i.e., AZ = A ∩ (γ(B) ∪ I(B)). We claim AZ is an
alternating trail of even length. Clearly this implies the z(B) terms make a net contribution of 0.
To prove the claim assume AZ ∩ γ(B) is nonempty and denote it as Pi (x, β(B)). If B is a maximal
blossom we are using the same notation as the algorithm. Although B need not be maximal i and
x are still chosen according to the algorithm: If v ∈ B the case B = Bv holds. If v ∈
/ B the case
B 6= Bv holds (with the obvious modification that we require f ∈ A rather than f ∈ P ).
If B is light then AZ = P0 (x, β(B)). This follows since a light blossom has i = 0 (in both
cases); also I(B) = ∅ since M consists of loops. This shows AZ has even length. If B is heavy
then AZ = P1 (x, β(B)) + η(B). This follows since a heavy blossom has i = 1 (in both cases); also
I(B) = η(B) since M consists of loops. Again this shows AZ has even length.
♦

Claim 3 The base algorithm computes correct distances and shortest paths.
61

Proof: Since w(M ) = 0, Claim 2 shows the augmented matching weighs y(s) + y(v ′ ) = y(s) − y(v).
The definition of G′v shows this f -factor weighs the same as a maximum weight sv-path. Thus
y(v) − y(s) is the cost of a shortest sv-path.
The algorithm outputs the nonloops in the augmenting path of the hypothetical search. These
edges are exactly the nonloops of the optimum f -factor, since M consists of loops.
♦
Our second goal is to extend this representation to arbitrary conservative real-valued cost functions. We accomplish this using a symbolic execution of the base algorithm, as follows.
Conceptually increase each edge cost c(e) by the same unknown positive quantity ǫ. The
algorithm will maintain all numeric quantities as expressions of the form r + sǫ, where r and s are
known real-valued quantities and ǫ is a symbol. The algorithm maintains the invariant that the same
sequence of grow, blossom, expand, and dual adjustment steps is executed for all sufficiently small
positive values of ǫ. (The execution for these sufficiently small values uses real-valued quantities
as usual, i.e., no symbolic quantities. We assume that any ties are broken the same way in every
execution.)
The invariant implies that the same sequence of grow, blossom, and expand steps can be done
when ǫ = 0. In proof observe that at any point in the algorithm an edge has slack sǫ (for arbitrary
s) iff setting ǫ = 0 makes the slack 0, i.e., the edge is tight. These tight edges can be processed
in any order when ǫ = 0, but they must all be processed before any others become tight. The
algorithm does this, i.e., all edges with slack sǫ become tight and are processed before any others
with slack having r > 0. Thus the same sequence of steps is executed for ǫ = 0.
To illustrate the workings of the base algorithm consider the computation of δ1 in a dual
adjustment step. Each quantity |c
y z(e) − w(e)| in the set defining δ1 is a linear combination of
quantities y(e), z(B), and w(e), all of the form r + sǫ. Hence it too has that form. To find δ1 , the
minimum quantity, the algorithm declares r + sǫ < r ′ + s′ ǫ exactly when (r, s) precedes (r ′ , s′ ) in
lexicographic order. If r = r ′ this is true for any ǫ > 0. This also holds if r < r ′ and s ≤ s′ . In
the remaining case r < r ′ and s > s′ , it holds for sufficiently small ǫ, i.e., 0 < ǫ < (r ′ − r)/(s − s′ ).
Clearly δ1 , as well as δ and the updated expressions for y and z, all have the desired form r + sǫ.
When the algorithm halts, setting ǫ to 0 gives valid duals y, z with matching M the set of all
loops and corresponding blossoms. This gives the desired representation.
As mentioned the final search structure S is a succinct representation of all shortest paths from
a fixed source s. Our third goal is to verify this is the gsp-structure.
To do this we will use two additional properties of S. Every loop vv is tight and belongs to S,
since vv ∈ M yet vv ∈
/ Pv implies vv is in the augmenting path of the hypothetical search for v.
Furthermore wlog vv is a blossom. In proof v is not an atom, since τ (v) unmatched would make
v inner. If the minimal blossom B containing v has v atomic in C(B) we can declare vv a loop
blossom with z(vv) = 0. η(vv) can be chosen as either of the unmatched edges of δ(v, C(B)).
A formal definition of the “generalized shortest path structure” is presented in Gabow and
Sankowski [21]. The structure is simply the search structure S with the matched loops removed.
To give a brief verification, the overall structure S is a tree whose nodes are contracted blossoms
that collectively contain all the vertices of G. (Note that a node may consist of a single vertex of
G, i.e., a contracted loop. When all edge costs are nonnegative every node is such a vertex, and
the gsp-structure is the usual shortest-path tree.) The rest of S is represented as a collection of
cycles, corresponding to Definitions 4.2 and 5.1 of blossom and the blossom tree T (B). The base
edges of blossoms are used as pointers to follow shortest paths, as in our definition of the Pi trails.
(These pointers are called edge τ (N ) for blossom N in [21]; the base vertex of N is called tN .)
The gsp-structure also has numeric labels that prove its validity. To describe these first note
62

that every edge of G is unmatched and so satisfies ycz(uv) ≥ w(uv), with equality for every edge of
S (this includes loops). Equivalently
d(u) + d(v) + c(uv) = y(u) + y(v) − 2y(s) − w(uv) ≥ −z{B : uv ∈ γ(B) ∪ η(B)} − 2y(s)

with equality on S. Define z ′ : 2V → R by z ′ (B) = −z(B), z ′ (V ) = −2y(s) to get
d(u) + d(v) + c(uv) ≥ z ′ {B : uv ∈ γ(B) ∪ η(B)}
with equality for every edge of the representation (including loops). This is the exact relation
satisfied by the labels of the gsp-structure, where d labels each vertex, z ′ labels each node as well
as V with z ′ (B) ≤ 0 for every B 6= V .
For the last goal assume the given cost function c is integral-valued, as is the case in algorithms.
We will simply execute the base algorithm using an integral blow-up of c. Another approach would
be symbolic execution as given above. We prefer using integral values, since we have given a
complete efficiency analysis of this case. (For instance Appendix B shows the numbers computed
by the algorithm are acceptably small. We have not analyzed the size of the s coefficients in the
symbolic execution.)
Define the cost function
c′ = 4nc + 1.
c′ has no 0-cost cycles. For any v, a shortest sv-path wrt c′ is a shortest sv-path wrt c that
in addition has the smallest length possible. We execute the base algorithm using c′ . Clearly
this algorithm can answer shortest path queries for c. (Also the base algorithm verifies that c
is conservative – if not it returns a matching with negative cost.) However we wish to find the
complete gsp-representation, which uses the optimum dual functions y, z for its numerical labels.
(These labels complete the representation since they provide a simple check that c is conservative.)
So our algorithm for general cost functions requires one more step, to transform the duals given by
the algorithm for c′ to those for c.
The extra step uses the following terminology. For any duals y, z and corresponding blossom
structure, define the function Z on blossoms B by
Z(B) = z{A : A ⊇ B, A a blossom}.
Obviously Z uniquely defines the dual function z via the relations z(B) = Z(B) − Z(p(B)) for p(B)
the parent of B in the blossom tree, with the convention Z(p(B)) = 0 for every maximal blossom
B.
Also call any edge e a witness for blossom B if e ∈ C(B) and Z(B) = w(e) − y(e). Any edge
of e ∈ C(B) is tight, i.e., w(e) = ycz(e) = y(e) + z{A : e ∈ γ(A) ∪ I(A)}. So e is a witness for B
if B is the minimal blossom containing both ends of e and e ∈
/ I(A) for any blossom A ⊂ B. In
general B may not have a witness. But a blossom at the end of our algorithm does have a witness.
In proof first note this is clear if C(B) is just a loop. So assume C(B) contains r nodes, r > 1.
The node α(B) does not have its base edge in C(B) (this base edge may not even exist). So the r
nodes collectively have at most r − 1 base edges in C(B). C(B) has r edges that are not loops. So
at least one of these edges, say e, is not the base edge of either of its ends. Since e is unmatched
this implies e ∈
/ I(A) for any blossom A. Since B is the minimal blossom containing both ends of
e, e is a witness for B.
The algorithm defines the desired duals as follows. Let y ′ , z ′ be the given duals for c′ , and y, z
the desired duals for c. To construct y, z first do an extra dual adjustment step to make y ′ (s) a
multiple of 4n. (In other words use δ = y ′ (s)− 4n⌊y ′ (s)/4n⌋ in a dual adjustment step. Let y ′ , z ′ , Z ′
63

now denote these adjusted duals.) The base algorithm provides the optimum f -factor for v, call it
Pv . The new algorithm defines
y(v) = −w(Pv ) + y ′ (s)/4n for every vertex v ∈ V
Z(B) = w(e) − y(e)
for every blossom B and e a witness for B
Also z is the dual function corresponding to Z.
Lemma 5.13 The above functions y, z are valid optimum duals. Specifically they satisfy (I4) for
the unmodified weight function w = −c and the f -factor M and blossoms found by the algorithm.
Proof: Let w′ denote the modified weight function used in the algorithm, i.e.,
(
1 e an edge of G
w′ (e) = 4nw(e) − µ(e) where µ(e) =
0 e a loop.
(Recall w(e) = 0 for e a loop.) Let ℓ(Pv ) be the length of the sv-path contained in Pv . So
y ′ (v) = −w′ (Pv ) + y ′ (s) = −4nw(Pv ) + ℓ(Pv ) + y ′ (s). Thus
y ′ (v) = 4ny(v) + ℓ(Pv ).
Take any blossom B and any witness e = uv ∈ C(B). So
(5.14)

Z ′ (B) = w′ (e) − y ′ (e) = (4nw(e) − µ(e)) − 4ny(e) − ℓ(Pu ) − ℓ(Pv )
= 4nZ(B) − r(B)

where
0 ≤ r(B) ≤ 2n − 1.
Although there may be several choices for e, (5.14) shows Z(B) is uniquely defined, since the
interval [Z ′ (B), Z ′ (B) + 2n − 1] contains a unique multiple of 4n.
Next observe that z(B) is nonnegative:
4nz(B) = 4n(Z(B) − Z(p(B))) = Z ′ (B) + r(B) − Z ′ (p(B)) − r(p(B))
= z ′ (B) + r(B) − r(p(B)) ≥ −(2n − 1).
The last inequality follows since z ′ (B) ≥ 0 and r(p(B)) ≤ 2n − 1 (even if B is maximal). Clearly
4nz(B) ≥ −(2n − 1) implies z(B) ≥ 0.
′ z ′ (e) and
Finally we show (I4) for any edge e = uv (including loops). Let σ ′ = w′ (e) − yd
σ = 4n(w(e) − ycz(e)). We claim
|σ ′ − σ| ≤ 4n − 2.

The claim gives the desired conclusion (I4). In proof consider two cases. If e is tight wrt y ′ , z ′ then
σ ′ = 0. Since σ is a multiple of 4n the claim shows it must be 0, so e is tight wrt y, z. If e is not
tight then σ is not uniquely determined, but the claim shows σ cannot have opposite sign from σ ′ .
Thus either e is dominated wrt both pairs of duals or underrated wrt both.
To prove the claim let Bu be the minimal blossom containing u and similarly for Bv . Consider
two cases.
Case e is not the base edge of both Bu and Bv : This case implies there is a blossom B such that
{A : e ∈ γ(A) ∪ I(A)} = {A : A ⊇ B, A a blossom}. In proof, if e is a loop then clearly we can
64

take B as Bu = Bv . If e is a nonloop witness for a blossom B then B is the desired blossom. If
e = η(Bu ) 6= η(Bv ) then B = Bu .
Using blossom B we have
σ ′ = w′ (e) − y ′ (e) − Z ′ (B) = 4n(w(e) − y(e) − Z(B)) − µ(e) − ℓ(Pu ) − ℓ(Pv ) + r(B) = σ ± r
where 0 ≤ r ≤ 2n − 1. The claim follows since 2n − 1 ≤ 4n − 2.
Case e = η(Bu ) = η(Bv ): Let B be the minimal blossom containing both u and v. Thus e = η(A)
for every blossom A with u ∈ A ⊂ B or v ∈ A ⊂ B. Clearly {A : e ∈ γ(A) ∪ I(A)} = {A :
A a blossom containing Bu or Bv }. Thus
σ ′ = w′ (e) − y ′ (e) − Z ′ (Bu ) − Z ′ (Bv ) + Z ′ (B)
= 4n(w(e) − y(e) − Z(Bu ) − Z(Bv ) + Z(B)) − 1 − ℓ(Pu ) − ℓ(Pv ) + r(Bu ) + r(Bv ) − r(B)
=σ±r
where 0 ≤ r ≤ 4n − 2. The claim follows.

✷

We conclude that the general algorithm is correct.
Regarding efficiency since f (V ) < 2n the complete execution of the f -factor algorithm runs
in time O(n(m + n log n)). This dominates the total time. For a more precise estimate, the set
N of negative edges for a conservative cost function is acyclic, so |N | < n. Let W be the largest
magnitude of a given cost. Initialize the dual functions by z ≡ 0 with no blossoms and
(
W d(v, N ) > 0
y(v) =
0
d(v, N ) = 0
Match every loop vv where y(v) = 0. Now the f -factor algorithm performs O(|N |) searches, using
time O(|N |(m + n log n)) assuming N 6= ∅. This again dominates the time.
Theorem 5.14 The generalized shortest path structure representing all shortest paths from s is
the f -factor algorithm search structure S. It can be constructed in time O(n(m + n log n)). More
generally if N 6= ∅ is the set of negative cost edges the time is O(|N |(m + n log n)).
The first time bound is given in Gabow and Sankowski [21]. The second bound shows how the
time increases with more negative edges. For example in a graph with O(1) negative edges the
algorithm is as fast as Dijkstra’s algorithm, which allows no negative edges.
A similar dependence on negative edges holds for conservative directed graphs: The single source
shortest path problem can be solved in time O(nN (m + n log n)), for nN the number of vertices
incident to a negative edge. In contrast the Bellman-Ford algorithm runs in time O(nm) with no
dependence on N . To achieve our time bound we model the digraph G as an undirected graph: The
vertex set is {v1 , v2 : v ∈ V (G) − s} + s2 ; the edge set is {v1 v2 : v ∈ V (G) − s} ∪ {u2 v1 : uv ∈ E(G)},
with c(v1 v2 ) = 0, c(u2 v1 ) = c(uv), f (v) = 1 for every vertex. The initialization sets y to W (the
largest magnitude of a given cost) if v is on a negative edge else 0. The initial matching consists of
the edges v1 v2 where v is not on a negative edge.

Acknowledgments
The author thanks Bob Tarjan for some fruitful early conversations, as well as Jim Driscoll. Also
thanks to an anonymous referee for a careful reading and many suggestions.
65

References
[1] A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms,
Addison-Wesley, Reading, Mass., 1974.
[2] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Saddle River, New Jersey, 1993.
[3] R.P. Anstee, “A polynomial algorithm for b-matchings: an alternative approach”, Information
Processing Letters, 24, 1987, pp. 153–157.
[4] M.O. Ball and U. Derigs, “An analysis of alternative strategies for implementing matching
algorithms”, Networks 13, 4, 1983, pp. 517–549.
[5] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver, Combinatorial Optimization, Wiley and Sons, NY, 1998.
[6] R. Cole and R. Hariharan, “Dynamic LCA queries on trees”, SIAM J. Comput., 34, 4, 2005,
pp. 894–923.
[7] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd Ed.,
McGraw-Hill, NY, 2001.
[8] W.H. Cunningham and A.B. Marsh, III, “A primal algorithm for optimum matching”, Math.
Programming Study 8, 1978, pp. 50–72.
[9] J. Edmonds, “Maximum matching and a polyhedron with 0,1-vertices”, J. Res. Nat. Bur.
Standards 69B, 1965, pp. 125–130.
[10] M.L. Fredman and R.E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, J. ACM, 34, 3, 1987, pp. 596–615.
[11] H.N. Gabow, “Implementations of algorithms for maximum matching on nonbipartite graphs”,
Ph. D. Dissertation, Comp. Sci. Dept., Stanford Univ., Stanford, Calif., 1973.
[12] H.N. Gabow, ”An efficient implementation of Edmonds algorithm for maximum matching on
graphs”, J. ACM, 23, 2, 1976, pp. 221–234.
[13] H.N. Gabow, “An efficient reduction technique for degree-constrained subgraph and bidirected
network flow problems”, Proc. 15th Annual ACM Symp. on Theory of Comp., 1983, pp. 448–
456.
[14] H.N. Gabow, “A scaling algorithm for weighted matching on general graphs”, Proc. 26th
Annual Symp. on Found. of Comp. Sci., 1985, pp. 90–100.
[15] H.N. Gabow, “Data structures for weighted matching and nearest common ancestors with
linking”, Proc. 1st Annual ACM-SIAM Symp. on Disc. Algorithms, 1990, pp. 434–443.
[16] H.N. Gabow, ”A data structures for nearest common ancestors with linking”, in preparation.
[17] A.M.H. Gerards, “Matching”, in Network Models (M.O. Ball, T.L. Magnanti, C.L. Monma,
G.L. Nemhauser, eds.), Elsevier, Amsterdam, 1995, pp. 135–224.

66

[18] H.N. Gabow, Z. Galil and T.H. Spencer, “Efficient implementation of graph algorithms using
contraction”, J. ACM, 36, 3, 1989, pp. 540–572.
[19] H.N. Gabow, Z. Galil, T.H. Spencer and R.E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs”, Combinatorica 6, 2, 1986, pp. 109–122.
[20] Z. Galil, S. Micali and H.N. Gabow, “An O(EV log V ) algorithm for finding a maximal
weighted matching in general graphs”, SIAM J. Comput., 15, 1, 1986, pp. 120–130.
[21] H.N. Gabow and P. Sankowski, “Algebraic algorithms for b-matching, shortest undirected
paths, and f -factors,” Proc. 54th Annual Symp. on Found. of Comp. Sci., 2013, pp. 137–146.
Revised version, 2016: “Algorithms for weighted matching generalizations I: Bipartite graphs,
b-matching, and unweighted f -factors”; “Algorithms for weighted matching generalizations II:
f -factors and the special case of shortest paths”.
[22] 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.
[23] H.N. Gabow and R.E. Tarjan, “Faster scaling algorithms for general graph matching problems”, J. ACM 38, 4, 1991, pp. 815–853.
[24] D. Harel and R.E. Tarjan, “Fast algorithms for finding nearest common ancestors”, SIAM J.
Comput., 13, 2, 1984, pp. 338–355.
[25] H.W. Kuhn, “The Hungarian method for the assignment problem”, Naval Res. Logist. Quart.,
2, 1955, pp. 83–97.
[26] H.W. Kuhn, “Variants of the Hungarian method for assignment problems”, Naval Res. Logist.
Quart., 3, 1956, pp. 253–258.
[27] E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
[28] J.B. Orlin, “A faster strongly polynomial minimum cost flow algorithm”, Operations Research,
41, 1993, pp. 338–350.
[29] L. Lovász and M.D. Plummer, Matching Theory, North-Holland Mathematic Studies 121,
North-Holland, New York, 1986.
[30] S. Pettie, “Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time”,
Proc. 16th Int. Symp. on Algorithms and Comp., 2005, X. Deng and D. Du eds., SpringerVerlag LNCS 3827, pp. 964–973.
[31] W.R. Pulleyblank, Faces of matching polyhedra, Ph.D. Diss., Department of Combinatorics
and Optimization, Univ. of Waterloo, 1973.
[32] W.R. Pulleyblank, “Edmonds, matching and the birth of polyhedral combinatorics”, Documenta Mathematica, 2012, pp. 181–197.
[33] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity,
Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982.
[34] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, NY, 2003.
67

[35] R.E. Tarjan, “Applications of path compression on balanced trees”, J. ACM, 26, 4, 1979, pp.
690–715.
[36] R.E. Tarjan, Data Structures and Network Algorithms, SIAM, Philadelphia, PA., 1983.
[37] M. Thorup, “Undirected single-source shortest paths with positive integer weights in linear
time”, J. ACM, 46, 3, 1999, pp. 362–394.
[38] G.M. Weber, “Sensitivity analysis of optimal matchings”, Networks 11, 1981, pp. 41–56.

68

A

Dual adjustment step for Edmonds’ algorithm

To state the dual adjustment step we first review the linear program for perfect matching. Its
variables are given by the function x : E → R+ which indicates whether or not an edge is matched.
The following linear program for maximum matching uses our summing convention, e.g., x(δ(v)) =
P
e∈δ(v) x(e).
P
maximize e∈E w(e)x(e) subject to
x(δ(v)) = 1
for every v ∈ V
|B|
x(γ(B)) ≤ ⌊ 2 ⌋ for every B ⊆ V
x(e)
≥ 0
for every e ∈ E

The dual LP uses dual functions y : V → R, z : 2V → R+ . Define ycz : E → R by

(A.1)

ycz(e) = y(e) + z{B : e ⊆ B}.

(Note for e = vw, y(e) denotes y(v) + y(w) and z{B : e ⊆ B} denotes
P
minimize y(V ) + B⊆V ⌊ |B|
2 ⌋ z(B) subject to

P

e⊆B

z(B).)

ycz(e) ≥ w(e) for every e ∈ E
z(B) ≥ 0
for every B ⊆ V

e is tight when equality holds in its constraint, i.e., ycz(e) = w(e). The algorithm maintains the
complementary slackness conditions:
x(e) > 0 =⇒ e is tight.
z(B) > 0 =⇒ x(γ(B)) = ⌊ |B|
2 ⌋.
In addition every edge in a blossom subgraph is tight (so blossoms can be rematched). It is easy
to see the following dual adjustment step maintains these conditions.
δ1 ← min{y(e) − w(e) : e = uv with u outer, v ∈
/ S}
δ2 = min{(y(e) − w(e))/2 : e = uv with u, v in distinct outer blossoms}
δ3 = min{(z(B)/2 : B an inner blossom of S}
δ = min{δ1 , δ2 , δ3 }
for every vertex v ∈ S do
if v is inner then y(v) ← y(v) + δ else y(v) ← y(v) − δ
for every blossom B in S do
if B is inner then z(B) ← z(B) − 2δ else z(B) ← z(B) + 2δ
Figure 15: Dual adjustment step in Edmonds’ algorithm.

B

Details for b-matching and f -factor algorithms

The LPs for b-matching are
Pthe obvious generalizations of ordinary matching:
maximize e∈E w(e)x(e) subject to
x(δ(v)) + 2x(γ(v)) = b(v)
for every v ∈ V
b(B)
x(γ(B))
≤ ⌊ 2 ⌋ for every B ⊆ V
x(e)
≥ 0
for every e ∈ E
69

minimize

P

v∈V

b(v)y(v) +

P

B⊆V

⌊ b(B)
2 ⌋ z(B) subject to

ycz(e) ≥ w(e) for every e ∈ E
z(B) ≥ 0
for every B ⊆ V

The complementary slackness conditions are essentially the same as ordinary matching:
x(e) > 0 =⇒ e is tight.
z(B) > 0 =⇒ x(γ(B)) = ⌊ |b(B)|
2 ⌋.
As mentioned in Section 4.1 complementary slackness requires that a blossom B with z(B) > 0
has precisely one incident matched edge, i.e., (4.4) holds. Let us review this fact. Our LP constraint
x(γ(B)) ≤ ⌊b(B)/2⌋ is redundant if b(B) is even (since 2x(γ(B)) ≤ x{δ(v) : v ∈ B} + 2x{γ(v) : v ∈
B} = b(B)). So we can assume b(B) is odd. Now equality in the constraint amounts to (4.4).
The dual adjustment step differs from ordinary matching only in allowing a loop to cause a
blossom (Fig.16). Like ordinary matching, the numerical quantities in our algorithm are always
half-integers. More precisely assume all given weights w(e) are integral. Assume either every initial
y-value is integral or every initial y-value is integral plus 1/2; furthermore every initial z-value is
integral. This assumption holds for common initializations, e.g., y ≡ maxe∈E w(e)/2 and z ≡ 0.
It also holds for the initialization in our strongly polynomial algorithm, Section 4.4. (Note the yvalues for BG, i.e., the transportation problem, are integral-valued. So (4.6) gives integral y-values
for our algorithm assuming we double the given weight function.) We will show that throughout
the algorithm
(B.1)

(∀v ∈V )(y(v) ∈ Z/2) and (∀B ⊆V )(z(B) ∈ Z).

To prove (B.1) assume it holds before a dual adjustment. Examining the changes of Fig.16 shows
it suffices to prove δ is a half-integer. Clearly δ1 and δ3 are half-integers. We will show any edge
joining two vertices of S has integral y-value. This makes δ2 half-integral and completes the proof.
Any tight edge has ycz(e) = w(e). So (B.1) (specifically the integrality of z) implies y(e) ∈ Z.
Any vertex v in S is joined to a free vertex x by a path P of tight edges. Thus y(v) + 2y{u : u ∈
P − v − x} + y(x) ∈ Z, i.e., y(v) + y(x) ∈ Z. Taking any other vertex v ′ of S with similar relation
y(v ′ ) + y(x′ ) ∈ Z gives y(v) + y(v ′ ) + y(x) + y(x′ ) ∈ Z. A free vertex is always outer, so its y-value
always decreases by δ. So the initialization implies y(x) + y(x′ ) ∈ Z. Thus y(v) + y(v ′ ) ∈ Z as
desired.
The magnitude of numbers computed by the algorithm can be bounded as follows. Let W be
the largest magnitude of an edge weight. Assume all initial y values are ≤ W and z ≡ 0. We claim
the largest value of ∆ is ≤ W b(V ). Clearly this implies every y and z value is ≤ 2W b(V ).
To prove the claim consider any point in the algorithm. Let b′ (v) be the remaining degree
requirement at v, i.e., b′ (v) = b(v) − d(v, M ) for M the current matching. Since every matched
edge is tight,
X
X
X
(B.2)
w(M ) =
ycz(e) =
d(v, M )y(v) +
⌊|B|/2⌋z(B).
e∈M

v∈V

B∈B

P
Thus we can rewrite the current value of the dual objective function as v∈V b′ (v)y(v) + w(M ).
The dual adjustment preserves tightness of the edges of M . So (B.2) holds and the updated dual
objective can be rewritten the same way. Thus the dual adjustment decreases the dual objective
value by b′ (V )δ ≥ 2δ. The initial dual objective is ≤ b(V )W . The final objective is P
the weight of a
maximum b-matching, which is ≥ −W b(V )/2 ≥ −W b(V ). So we always have ∆ =
δ ≤ b(V )W .
As with ordinary matching, other versions of weighted b-matching have LPs that are minor
modifications of the original. Correspondingly, minor modifications of our algorithm find such
70

δ1 ← min{y(e) − w(e) : e = uv ∈
/ M with Bu outer, Bv ∈
/ S}
δ2 = min{(y(e) − w(e))/2 : e = uv ∈
/ M with Bu , Bv outer, either Bu 6= Bv or u = v atomic}
δ3 = min{z(B)/2 : B an inner blossom of S}
δ = min{δ1 , δ2 , δ3 }
for every vertex v ∈ S do
if Bv is inner then y(v) ← y(v) + δ else y(v) ← y(v) − δ
for every blossom B in S do
if B is inner then z(B) ← z(B) − 2δ else z(B) ← z(B) + 2δ
Figure 16: Dual adjustment step for b-matching.

matchings. We illustrate with maximum cardinality maximum weight b-matching (defined in Section 4.3). It is convenient to treat the more general problem of finding a b-matching of maximum
weight subject to the constraint that it contains exactly k edges.
The primal LP relaxes the vertex degree constraint to
x(δ(v)) + 2x(γ(v)) ≤ b(v)

for every v ∈ V

and adds the cardinality constraint
x(E) = k.
The dual problem has a variable c for the cardinality constraint, the left-hand side of the dual edge
constraint changes from ycz(e) to ycz(e) + c, and the nonnegativity constraint y(v) ≥ 0 is added.
The additional complementary slackness constraint is
y(v) > 0 =⇒ x(δ(v)) + 2x(γ(v)) = b(v)

for every v ∈ V.

To find such a matching we initialize our algorithm using a common value for every y(v). The
algorithm halts after the search that increases the matching size to k. For maximum cardinality
maximum weight b-matching, this is the first time a search fails. To get an optimal LP solution,
let Y be the common final value for y(v), v free, or 0 if no such vertex exists. (Fig.16 implies that
throughout the algorithm all free vertices have the same y-value, and this value is the minimum
y-value.) Decrease all y values by Y and set c = 2Y . This solves the new LP. (In the dual edge
constraint the new y-values decrease ycz(e) by 2Y , which is balanced by the new LP term c = 2Y .)
We conclude that our algorithm is correct. It also proves the LP formulation is correct.
The LPs for f -factors incorporate limits on the number of copies of an edge as well as I(B) sets
of blossoms. (The graph may have parallel edges, so wlog we allow only 1 version of each copy to
be in the f -factor.)
P
maximize e∈E w(e)x(e) subject to
x(δ(v)) + 2x(γ(v))
x(γ(B) ∪ I)
x(e)
x(e)

=
≤
≤
≥

f (v)
⌋
⌊ f (B)+|I|
2
1
0

for
for
for
for

every
every
every
every

v∈V
B ⊆ V, I ⊆ δ(B)
e∈E
e∈E

The dual LP uses dual functions y : V → R, z : 2V × 2E → R+ . Define ycz : E → R by

(B.3)

ycz(e) = y(e) + z{(B, I) : e ∈ γ(B) ∪ I}.
71

minimize

P

v∈V

f (v)y(v) +

P

B⊆V,I⊆δ(B) ⌊

f (B)+|I|
⌋ z(B, I)
2

+ u(E) subject to

ycz(e) + u(e) ≥ w(e) for every e ∈ E
u(e)
≥ 0
for every e ∈ E
z(B, I)
≥ 0
for every B ⊆ V, I ⊆ δ(B)
In our algorithm every nonzero z value has the form z(B, I(B)) for B a mature blossom. So we
use the notation z(B) as a shorthand for z(B, I(B)).
Say that e is dominated, tight, or underrated depending on whether ycz(e) is ≥ w(e), = w(e), or
≤ w(e), respectively; strictly dominated and strictly underrated refer to the possibilities > w(e) and
< w(e) respectively. The complementary slackness conditions for optimality can be written with u
eliminated as
x(e) > 0 =⇒ e is underrated
x(e) = 0 =⇒ e is dominated
⌋.
z(B) > 0 =⇒ x(γ(B) ∪ I(B)) = ⌊ f (B)+|I(B)|
2
The numbers computed by the algorithm are analyzed similar to b-matching. The same argument applies to show the algorithm always works with half-integers. The same bound holds for the
magnitude of numbers. The only addition to the analysis is to account for the term u(E) in the
dual objective function. Clearly the optimum u function is defined by setting u(e)
P equal to the slack
in e, w(e) − ycz(e), for every edge e ∈ M . So (B.2) has the analog, w(M ) = e∈M ycz(e) + u(e) =
P
P
f (B)+I(B)
⌋z(B) + u(E). This equation holds both before and after the
v∈V d(v, M )y(v) +
B∈B ⌊
2
dual adjustment. (Note the dual adjustment will change u values
P also, and each u(e) may increase.)
The dual objective function can be rewritten just as before, as v∈V f ′ (v)y(v)+ w(M ), both before
and after the adjustment step. The rest of the analysis is identical to b-matching.
Similar to b-matching our algorithm extends to variants of the maximum f -factor problem. We
again illustrate with maximum cardinality maximum weight partial f -factors. The LP is modified
exactly as in b-matching. Our modified algorithm and the definition of new LP variables is exactly
the same. The only difference in the analysis is that the new complementary slackness conditions
for edges are
x(e) > 0 =⇒ ycz(e) + c ≤ w(e)
x(e) = 0 =⇒ ycz(e) + c ≥ w(e).
As before the quantity ycz(e) + c equals the algorithm’s value of ycz(e), so these conditions are
equivalent to the original ones.

C

Grow/Expand steps

We give a simple data structure to handle grow and expand steps. First consider ordinary matching.
At any point in a search, for any vertex v ∈ V define slack(v) to be the smallest slack in an
unmatched edge from an outer node to v. If v ∈
/ S and slack(v) < ∞, dual adjustments reduce
slack(v). When slack(v) becomes 0 a grow step can be performed to make Bv inner. But if Bv is
a blossom, it may become inner before slack(v) becomes 0. This blossom may later get expanded,
and v may leave S. If not some smaller blossom containing v may get expanded causing v to leave
S. Continuing in this fashion v may oscillate in and out of S, becoming eligible and ineligible for
grow steps. This makes tracking potential grow steps nontrivial. Note there is no such complication
for grow steps using a matched edge to add a new outer node, since matched edges are always tight
and outer nodes never leave S.
The same overview applies to b-matching. f -factors are more general, since matched edges need
not be tight. We first present the algorithm that applies to ordinary matching and b-matching.
72

Then we extend the algorithm to f -factors.
Data structures As in Section 2.2 for ordinary matching and 4.1 for b-matching and f -factors,
we use a tree representing the laminar structure of blossoms. Specifically at the start of a search
the current blossoms (from previous searches) form a tree B. The root of B corresponds to V , and
each leaf corresponds to a vertex of G. The children of B in B are the blossoms and atoms in the
cycle C(B) forming B. The subtree of a blossom B has size O(|V (B)|), as in Sections 2.2 and 4.1.
Recall (Section 3.1) the rank of a B-node B is r(B) = ⌊ log |V (B)|⌋. A B-child of B is small if
it has rank < r(B), else big. Clearly B has at most one big child. So the rank r(B) descendants of
B form a path P starting at B. Each node on P except B is the big child of its parent.8 The data
structure marks each node as big or small.
We also use this notion: A child of a node on the above path P is a small component of B.
Clearly a small component of B is a small child of its parent. If B is a blossom then V (B) =
∪{V (A) : A a small component of B}. (This fails if B is a leaf of B. Such a B has no children or
components.)
The main task for the data structure is tracking slack(v) values. Obviously this requires tracking
Bv (as usual Bv denotes the currently maximal blossom or atom containing v). The values node(v)
defined below allow identifying Bv in O(1) time. node(v) values are also used in blossom and
augment steps to compute paths in S.
Recall the data structure for numerical quantities given in the last subsection of Section 4.3, in
particular these definitions: ∆ is the sum of all dual adjustment quantities δ in the current search.
Any outer vertex v has a quantity Y (v), such that the current value of y(v) is Y (v) − ∆. A global
Fibonacci heap F has entries for candidate grow, blossom, and expand steps, with key equal to the
value of ∆ when the corresponding edge becomes tight.
To compute current y and z values for nonouter nodes, we use an auxiliary quantity DEL(B)
that tracks z-values of expanded blossoms that have been converted into y-values. To define this
quantity let y0 and z0 denote the dual functions at the start of the current search. The algorithm
stores the quantity
Y (v) = y0 (v).
Every node B of B is labelled with the quantity
(C.1)

DEL(B) =

1
2

z0 {A : A a proper ancestor of B in B}.

Observe that when B is a maximal blossom, DEL(B) is equal to the total of all dual adjustments
made while B was properly contained in an inner blossom. At any point in time current y values
are computed by
(
Y (v) + DEL(Bv )
Bv not in S
(C.2)
y(v) =
Y (v) + DEL(Bv ) + ∆ − ∆0 (Bv ) Bv an inner node
where ∆0 (B) denotes the value of ∆ when blossom B became an inner node (blossom or atom).
We will compute y(v) in O(1) time when it is needed. To do this we must identify Bv in O(1) time.
This is done using the pointer node(v), as we will describe below.
We track the best candidate edges for grow steps from outer nodes using a system of Fibonacci
heaps. At any point in the algorithm every maximal nonouter blossom B has a Fibonacci heap
FB . The nodes of FB are the small components of B. Thus if B is not a node of S, the smallest
8

P is a slight variant of the “heavy path” of [24, 35].

73

slack of an unmatched edge for a grow step to B is the smallest value slack(v), v a vertex in V (A),
A a blossom or atom with a node in FB .
The data structure must also handle maximal nonouter atoms B. For uniformity we assume
atoms are handled like blossoms – they have a Fibonacci heap of one node, the atom itself. We will
not dwell on this case, the reader can make the obvious adjustments for maximal nonouter atoms.
Returning to the general case, the data structure does not explicitly store values slack(v), since
they change with every dual adjustment. Instead we store offsetted versions of related quantities
as follows.
Observe that whenever Bv is not in S, the slack in an unmatched edge uv with Bu outer is
y(u) + y(v) − w(uv) = (Y (u) − ∆) + (Y (v) + DEL(Bv )) − w(uv).
(Note this relation holds regardless of prior history, i.e., when u was first in an outer node or the
pattern of v’s movement in and out of S.) So the data structure stores the quantity
SLACK(v) = min{Y (u) + Y (v) − w(uv) : Bu outer, uv ∈ E − M }
for every vertex v where Bv is not outer. Note that the expression for a given edge uv never changes
in value, even as Bu changes. The data structure also records the minimizing edge uv. SLACK(v)
and its minimizing edge are updated as new outer nodes are created. At any point in time when v
is not in S, the current value of slack(v) is
(C.3)

slack(v) = SLACK(v) − ∆ + DEL(Bv ).

The key of a node A in FB is
(C.4)

key(A, FB ) = min{SLACK(v) : v ∈ V (A)}.

At any point in time when B is not in S, the current smallest slack of an unmatched grow step
edge to B is f ind min(FB ) − ∆ + DEL(B). Thus a grow step for B can be done when ∆ =
f ind min(FB ) + DEL(B). So the key of B in the global heap F is f ind min(FB ) + DEL(B), if
B is not a node of S.
For every vertex v ∈ V , node(v) is the unique ancestor of v that is currently a node of some
heap FB . node(v) is used in (C.4) to maintain keys in FB (i.e., node(v) gives A in (C.4)). node(v)
is also used in (C.2) to determine the current blossom Bv . Specifically node(v) is in the heap FBv .
Algorithms When a new outer node B is created, every unmatched edge uv (u ∈ B) is examined.
SLACK(v) is decreased if appropriate. This may trigger a decrease key for node(v) in FBv . This
may in turn trigger a decrease key for Bv in F, if Bv is currently not in S.
When a grow step adds a blossom B to S, the node for B in F is deleted. Note that whether B
becomes inner or outer, it never gets reinserted in F in this search. If B becomes inner the value
∆0 (B) is recorded. If B becomes outer, the values y(v), v ∈ V (B) are required to redefine Y (v)
(recall from Section 4.3). This is done using the first alternative of (C.2). If B becomes inner and
later becomes outer in a blossom step, Y (v) is redefined using the second alternative of (C.2).
Consider an expand step for an inner blossom B. The B-children of B (i.e., the nodes of C(B))
become maximal blossoms or atomic, and we must update the data structure for them. Let B ′ be
the big B-child of B, if it exists. For every B-child A 6= B ′ of B, delete the node A of FB . Initialize
a new F-heap FA as follows (modifying appropriately if A is atomic):
For each small component D of A, create a node in FA . For every v ∈ V (D) update node(v)
to D. Assign key(D, FA ) ← min{SLACK(v) : v ∈ V (D)}.
74

Let the new heap FB ′ be the (updated) heap FB . Insert the B-children of B that are no longer
in S as entries in F. For the B-children that are inner nodes of S record their ∆0 value. Process
B-children that are outer nodes of S as above.
The main observation for correctness of the expand procedure is that FB ′ is the desired heap
for B ′ . This follows since the small components of B ′ are those of B minus the small children of B.
It is easy to see the total time used in the course of an entire search is O(m + n log n). When a
small child A becomes maximal it is charged O( log n) to account for its deletion from FB . For D a
small component of A, each vertex v ∈ V (A) is charged O(1) for resetting node(v) and examining
SLACK(v). (The new node(v) values are easily found by traversing the subtree of A in the blossom
tree B. The traversal uses time proportional to the number of leaves, i.e., O(1) time for each vertex
v.) v moves to a new small component O( log n) times so this charge totals O(n log n). Finally and
most importantly, decrease key uses O(1) amortized time in a Fibonnaci tree.
f -factors Two new aspects of f -factors are that matched edges needn’t be tight and edges can
be in I-sets. We will use some simple facts about I-sets.
Lemma C.1 Consider blossoms A, B with V (A) ⊆ V (B), and edge e ∈ δ(A) ∩ δ(B).
(i) e = η(A) ⇐⇒ e = η(B).
(ii) e ∈ I(A) ⇐⇒ e ∈ I(B).
Proof: (i) Consider three cases for A.
Case A 6⊆ α(B): This makes η(A) ∈ γ(B). So e ∈ δ(B) implies e 6= η(A). Also e ∈ δ(A) implies
e 6= η(B).
Case A = α(B): This makes η(A) = η(B). Hence e = η(A) iff e = η(B).
Case A ⊂ α(B): Edge e of the hypothesis is in δ(A) ∩ δ(α(B)). By induction e = η(A) ⇐⇒ e =
η(α(B)). Since η(α(B)) = η(B) this implies (i).
(ii) By (i) there are two possibilities:
Case e 6= η(A), η(B): e ∈ I(A) ⇐⇒ e ∈ M ⇐⇒ e ∈ I(B).
Case e = η(A) = η(B): e ∈ I(A) ⇐⇒ e ∈
/ M ⇐⇒ e ∈ I(B).

✷

Now observe an edge e = uv ∈ I(Bv ) has
(C.5) z0 {A : V (A) ⊆ V (Bv ), e ∈ I(A)} = z0 {A : v ∈ V (A) ⊆ V (Bv )} = 2(DEL(v) − DEL(Bv )).
The second equation is trivial and the first follows immediately part (ii) of the lemma.
The analog of the previous definition of slack is
(C.6)

slack(v) = min{|c
y z(uv) − w(uv)| : uv ∈ E eligible at u}.

(Recall Lemma 5.8 and its terminology.) As in Lemma 5.7 define a sign σ as −1 if uv ∈ M else
+1, so any edge uv has |c
y z(uv) − w(uv)| = σ(c
y z(uv) − w(uv)).
The highest level outline of the data structure is as before: We track slack by maintaining the
invariant (C.3), where the stored quantity SLACK(v) will be defined below. We define keys in
75

FB and F exactly as before, e.g., (C.4). The invariant implies that for any blossom B not in S,
the current smallest slack of a grow step edge to B is f ind min(FB ) − ∆ + DEL(B). So the data
structure gives the correct value for the next dual adjustment.
Our definition of SLACK(v) involves two quantities IU (uv) and IV (uv) that account for the
contributions of I-edges to the slack of uv, IU at the u end and IV at the v end. We will define
IU and IV to be fixed, stored quantities so the following relations hold. At any time when v ∈
/ S,
and Bv is the maximal blossom/vertex currently containing v,
(C.7)

y(v) + z{A : v ∈ V (A), uv ∈ I(A)} = Y (v) + IV (uv) + σDEL(Bv ).

At any time after uv becomes eligible at u,
(C.8)

y(u) + z{A : u ∈ V (A), uv ∈ I(A)} = Y (u) + IU (uv) − σ∆.

We reiterate that the only terms on the right-hand side of these two equations that change with
time are DEL(Bv ) and ∆.
Now define
SLACK(v) = min{σ(Y (u) + Y (v) + IU (uv) + IV (uv) − w(uv)) : uv ∈ E eligible at u}.
Let us show the above relations imply the desired invariant (C.3) for SLACK. Adding the two
equations and multiplying by σ implies that at any point in time when uv is eligible and v ∈
/ S,
|c
y z(uv) − w(uv)| = σ(Y (u) + IU (uv) + Y (v) + IV (uv) − w(uv)) − ∆ + DEL(Bv ).
Applying this for every edge uv in the definition of SLACK gives (C.3) as desired.
It remains to give IV and IU . The contribution at the nonouter end v is defined by


0
uv ∈
/ M ∪ η(Bv )



2DEL(v)
uv ∈ M − η(Bv )
IV (uv) =

2DEL(Bv )
uv = η(Bv ) ∈ M



2(DEL(v) − DEL(B )) uv = η(B ) ∈
v
v / M.

To discuss this definition we will use the following terminology. Recall that the algorithm
computes IV (uv) when uv becomes eligible at u. IV (uv) is defined using the blossom/vertex Bv
at that time. However we must verify (C.7) whenever v ∈
/ S, so Bv may change. To keep the two
cases straight say the defining Bv is used to compute IV (uv), and a useful Bv is one that may be
required later on in (C.7) to establish the invariant (C.3) for the algorithm. The defining Bv is
useful iff v ∈
/ S when IV (uv) is computed. Clearly a useful Bv is a subset of the defining Bv , but
we shall see that not every such Bv is useful.
To prove the definition is correct we will analyze each of its four cases separately. We will show
that if the defining Bv is in that case, so is every useful Bv . Then we will show (C.7) is satisfied
for every useful Bv . To do this we will compute the value of the left-hand side of (C.7) and deduce
the correct value of IV (uv) by comparing to the right-hand side.
To begin the analysis, note that whenever v ∈
/ S the current value of y(v) is
Y (v) + DEL(Bv )
since every dual adjustment increases y(v) by δ. Also when uv ∈ I(Bv ) the z contribution to the
left-hand side of (C.7) is
z0 {A : v ∈ V (A) ⊆ V (Bv )} = 2(DEL(v) − DEL(Bv )),
76

by (C.5).
Case uv ∈
/ M ∪ η(Bv ): We assume this case holds for the defining Bv . So for any useful Bv , say B,
uv is an unmatched edge and uv 6= η(B) (by Lemma C.1(i)). So this case holds for every useful B.
Now we establish (C.7) for any useful Bv . The contribution to the left-hand side of (C.7) is
y(v) = Y (v)+σDEL(Bv ). This follows since this case has uv ∈
/ I(Bv ) (so there is no z contribution)
and σ = 1 (since uv ∈
/ M ). Comparing to the right-hand side of (C.7) shows IV (uv) = 0, as desired.
Case uv ∈ M − η(Bv ): We assume this holds for the defining Bv . So any useful Bv has uv matched
and not its base edge (by Lemma C.1(i)). Thus this case holds for any useful Bv .
Now consider any useful Bv . If Bv is a blossom then uv ∈ I(Bv ). So the z contribution is
2(DEL(v) − DEL(Bv )). This also holds if Bv is atomic, since the z contribution is 0. Since
uv ∈ M , σ = −1. Adding the y and z contributions to the left-hand side of (C.7) gives total
contribution
(Y (v) + DEL(Bv )) + 2(DEL(v) − DEL(Bv )) = Y (v) + 2DEL(v) + σDEL(Bv ).
Thus IV (uv) = 2DEL(v), independent of Bv .
The next two cases have uv = η(Bv ) for the defining Bv . If v ∈ S at this point then wlog Bv is
inner. Since v = β(Bv ), v will remain in S for the rest of the search. So uv is irrelevant to the data
structure. If v ∈
/ S then Bv is itself the first useful Bv . The first time this Bv becomes a node of
S, the preceding argument applies. It shows there are no other useful Bv ’s. In summary we have
shown for the next two cases, every useful Bv belongs to the same case.
Case uv = η(Bv ) ∈ M : Since uv ∈
/ I(Bv ) there is no z contribution (by Lemma C.1(ii)). So
the total contribution is y(v) = Y (v) + DEL(Bv ) = Y (v) + 2DEL(Bv ) + σDEL(Bv ). Thus
IV (uv) = 2DEL(Bv ).
Case uv = η(Bv ) ∈
/ M : This makes uv ∈ I(Bv ) so there is a z contribution. The total contribution
is
(Y (v) + DEL(Bv )) + 2(DEL(v) − DEL(Bv )) = Y (v) + 2(DEL(v) − DEL(Bv )) + σDEL(Bv ).
Thus IV (uv) = 2(DEL(v) − DEL(Bv )).
Remark: It might seem that the cases for uv = η(Bv ) are subject to a simplification because
this edge is often tight. Specifically if Bv was not a maximal blossom at the beginning of the
current search then η(Bv ) is tight when the search starts. So η(Bv ) will be tight when Bv becomes
maximal. However this need not be the case when η(Bv ) becomes eligible. For instance suppose a
search starts out with the structure of Fig.17. Then the inner blossom B5 gets expanded to give
part of Fig.11, where α2 = η4 = η(B4 ). As mentioned (in the Examples section after Fig.14) a dual
adjustment makes α2 strictly underrated. A subsequent expansion of B3 may make α2 eligible, but
still underrated.
The contribution at the S end u is


DEL(Bu ) − ∆0 (Bu )



2DEL(u) − DEL(B ) + ∆ (B )
u
0
u
IU (uv) =

0



2 DEL(u) − DEL(B ) − 2∆ (O ) + ∆ (B )
u
0
u
0
u
77

Bu
Bu
Bu
Bu

inner, uv ∈ M
inner, uv = η(Bu ) ∈
/M
outer, uv ∈
/M
outer, uv ∈ M.

B5
B3

η3

η4

B4

Figure 17: Precursor to structure of Fig.11.
Ou is defined below.
To verify correctness let ∆0 be the value of ∆ when uv first becomes eligible for (any) Bu . We
will show (C.8) holds at that point. Thereafter, uv remains eligible (Lemma 5.8), so (5.5) shows
the left-hand side of (C.8) changes by −σδ in every dual adjustment, as does the right-hand side.
Thus (C.8) continues to hold in every dual adjustment.
Case Bu inner, uv ∈ M : This makes uv ∈
/ I(Bu ). (There are two cases: If Bu is a blossom then
uv = η(Bu ) since uv is eligible. If Bu is atomic then I(Bu ) = ∅.) Thus the contribution is
y(u) = Y (u) + DEL(Bu ) = Y (u) + DEL(Bu ) − ∆0 (Bu ) − σ∆0 .
Thus IU (uv) = DEL(Bu ) − ∆0 (Bu ).
Case Bu inner, uv = η(Bu ) ∈
/ M : This makes Bu a blossom and uv ∈ I(Bu ). The contribution for
y(u) is the same as the previous case. The contribution for z is 2(DEL(u) − DEL(Bu )). The total
contribution is (Y (u) + DEL(Bu )) + 2(DEL(u) − DEL(Bu )) = Y (u) + 2DEL(u) − DEL(Bu ) +
∆0 (Bu ) − σ∆0 . Thus IU (uv) = 2DEL(u) − DEL(Bu ) + ∆0 (Bu ).
We are left with the case where uv first becomes eligible when u enters an outer node. Furthermore uv 6= η(Bu ) when Bu is a blossom. To prove the latter, the preceding two cases apply if
blossom Bu enters S as inner. If Bu enters as outer clearly η(Bu ) = τ (Bu ) ∈ S.
Let Ou be the first outer node that contains Bu . Let ∆0 (Ou ) be the value of ∆ when Ou is
formed. So ∆0 = ∆0 (Ou ). Recall that when Ou is formed we redefine Y (u) to be the current value
of y(u) plus ∆0 (Ou ). Hence at any time after Ou is formed Bu is outer and
y(u) = Y (u) − ∆.
Also the only z contribution comes from Bu (since we assume ∆ = ∆0 ).
Case uv becomes eligible for Ou , uv ∈
/ M : There is no z contribution. (This is by definition
if Bu is atomic. If Bu is a blossom we have noted uv 6= η(Bu ).) So the total contribution is
y(u) = Y (u) − ∆0 (Ou ) = Y (u) − σ∆0 . Thus IU (uv) = 0.
78

Case uv becomes eligible for Ou , uv ∈ M : First suppose Bu is a blossom. This case makes
uv ∈ I(Bu ). When Bu becomes an S-node (outer or inner) the z contribution is
z0 {A : u ∈ V (A) ⊆ V (Bu )}.
If Bu enters as an inner node and is later absorbed in an outer node, this z contribution decreases
by
2(∆0 (Ou ) − ∆0 (Bu )).
This also holds if Bu enters as outer. (The latter may occur in a grow step that adds Bu = Ou , or
in an expand step that makes Bu maximal and outer.)
It is possible that Bu is an atom. We must have Bu outer, by the first case. An atom has no z
contribution. This is consistent with the two displayed z contributions, since they are both 0 for
an atom Bu (Bu = Ou ).
So in all cases, the left-hand side of (C.8) is
(Y (u) − ∆0 (Ou )) + 2(DEL(u) − DEL(Bu ) − (∆0 (Ou ) − ∆0 (Bu )))
= Y (u) + 2(DEL(u) − DEL(Bu ) − 2∆0 (Ou ) + ∆0 (Bu )) − σ∆0 .
Thus IU (uv) = 2(DEL(u) − DEL(Bu ) − 2∆0 (Ou ) + ∆0 (Bu )).
The only changes to the algorithm are the obvious ones for examining edges: Matched edges
must be examined and added to the data structure. IU and IV quantities must be computed. It
is easy to see the latter uses O(1) time per edge. So the timing estimate is not affected.

79

