What the Running-Time Bound Counts
Edmonds’ blossom method finds maximum matchings in general graphs by searching for augmenting paths while contracting odd cycles encountered during the search. Its implementation has several moving parts: a queue explores the alternating forest, parent links record how vertices were reached, and base labels track which original vertices currently represent contracted blossoms. To analyze the running time, we count how often these structures can be updated and how much work each update requires.
Throughout, \(G=(V,E)\) is a finite simple graph, \(n=|V|\), and \(m=|E|\). A matching is a set of pairwise vertex-disjoint edges. An augmenting path for a matching \(M\) is a path whose edges alternate between edges outside \(M\) and edges in \(M\), beginning and ending with edges outside \(M\), with both endpoints unmatched. Replacing the matching edges on such a path by its nonmatching edges increases the matching size by one.
We analyze a standard straightforward implementation using an adjacency matrix. Thus testing whether two vertices are adjacent takes constant time, and scanning all possible neighbors of one vertex takes \(O(n)\) time. This choice makes the operation count transparent; it gives a cubic bound without relying on a more specialized data structure.
The search grows an alternating forest from an unmatched root. An outer vertex is scanned for edges not in the matching. Such an edge can lead to an inner vertex; if that vertex is matched, its mate is added to the forest as an outer vertex. Finding an unmatched vertex at the other end gives an augmenting path. An edge joining two outer vertices in the same search can reveal an odd cycle, or blossom. The search contracts that blossom, updates the base labels and continues in the contracted representation. The correctness of this search and the expansion of a contracted blossom when augmenting were established in the earlier material on Edmonds’ blossom search and blossom augmentation. Here we count their computational cost.
Why Each Data Structure Matters
The queue makes the exploration breadth-first: each outer vertex is processed by removing it from the queue and scanning its potential neighbors. A parent link stores how a vertex entered the forest. Along with mate links, these parents let the algorithm reconstruct the alternating path, or the odd-cycle route that is contracted. The base array is essential after contraction: vertices that belong to one blossom are treated as a single representative when deciding whether an edge joins distinct outer bases.
A typical implementation also uses a Boolean marker to record whether a vertex has been reached in the current search, and a temporary marker when tracing parent chains to find a blossom's base. These arrays have \(O(n)\) entries. The adjacency matrix has \(n^2\) entries, so this implementation uses \(O(n^2)\) memory. The queue, parent, mate, base and marker arrays together use \(O(n)\) additional memory.
Cost of One Search
Proof. Fix one search. A vertex is marked when it is first reached, and the algorithm does not enqueue it a second time during that search. Therefore at most \(n\) vertices are removed from the queue. Each removal scans at most \(n\) possible neighbors in the adjacency matrix, for at most \(n\cdot n=n^2\) neighbor tests.
We also count contraction work. When a blossom is found, tracing parent links to locate the common base takes at most \(n\) steps, since a parent chain contains at most \(n\) vertices. Updating base labels and the associated markers takes at most \(n\) steps as well. Within a search, a contraction replaces at least three distinct current bases on an odd cycle by one base, reducing the number of current bases by at least two. Bases are not expanded during this search, so there are at most \(n-1\) contractions. Consequently, all parent tracing and all base updates together take \(O(n^2)\) time. Queue operations and other array updates take \(O(n)\) additional time. Thus one search takes \(O(n^2)\) time.
The standard root sweep makes at most \(n\) search attempts, because each vertex is considered as a root at most once, and a vertex already matched is skipped. Hence the total search time is at most \(n\cdot O(n^2)=O(n^3)\). An empty graph requires no searches; the stated bound concerns \(n\geq1\). \(\square\)
This is an upper bound: it does not claim that every graph takes cubic time. A search may stop as soon as it finds an augmenting path, and a graph may have few blossoms. The bound accounts for the largest amount of work the straightforward implementation can perform across its searches.
Worked Searches and Augmentations
Worked Example: An Augmenting Path Without a Blossom
Let \(V=\{1,2,3,4\}\), \(E=\{12,23,34\}\), and start with matching \(M=\{23\}\). The unmatched vertices include \(1\), so begin a search at root \(1\). Use the neighbor order \(2,3,4\).
| Operation | Queue after operation | Parent or matching information |
|---|---|---|
| Start at \(1\) | \([1]\) | \(1\) is the outer root |
| Scan \(1\), reach \(2\) | \([3]\) | \(2\) is inner, parent \(2=1\); mate \(2=3\), so \(3\) is outer |
| Scan \(3\), reach free \(4\) | \([]\) | Parent \(4=3\); the search finds an augmenting path |
The parent and mate links give the path \(1,2,3,4\). Its edges \(12,23,34\) are, in order, outside \(M\), inside \(M\), outside \(M\). Flipping membership along the path gives the new matching \(M'=\{12,34\}\).
Check: \(12\) and \(34\) have no common endpoint, so \(M'\) is a matching of size \(2\). The path has two edges outside the old matching and one inside it, so the size increases from \(1\) to \(1+2-1=2\), as required.
Worked Example: A Search That Contracts a Blossom
Let \(V=\{r,a,b,c,d,t\}\), \(E=\{ra,ab,bc,cd,db,dt\}\), and start with \(M=\{ab,cd\}\). The unmatched vertices are \(r\) and \(t\); start at \(r\). Choose adjacency orders so that the search from \(b\) examines \(c\) before any other new neighbor, and the search from \(d\) examines \(b\) before \(t\).
| Step | Queue or action | Forest information |
|---|---|---|
| Start | \([r]\) | \(r\) is the outer root |
| Scan \(r\) | \([b]\) | \(a\) is inner with parent \(a=r\); since \(ab\in M\), \(b\) is outer |
| Scan \(b\) | \([d]\) | \(c\) is inner with parent \(c=b\); since \(cd\in M\), \(d\) is outer |
| Scan \(d\) | Contract the blossom | The edge \(db\) joins outer vertices; the parent chains meet at \(b\) |
| Continue from \(d\) | Reach \(t\) | \(dt\notin M\) and \(t\) is free, so an augmenting path is found |
The odd cycle is \(b,c,d,b\), using edges \(bc,cd,db\). Its base is \(b\), the common point reached by the outer parent chains. Contraction represents \(b,c,d\) by that base while the search continues. On expansion, the augmenting path is \(r,a,b,c,d,t\). Its edges alternate as \(ra\notin M\), \(ab\in M\), \(bc\notin M\), \(cd\in M\), and \(dt\notin M\).
Flipping along the path gives \(M'=\{ra,bc,dt\}\). Check: these three edges cover the six distinct vertices \(r,a,b,c,d,t\) exactly once, so they form a matching of size \(3\). The original matching had size \(2\); the change is \(3-2=1\), as it must be for one augmentation.
Worked Example: Repeated Augmentations on a Path
Let \(V=\{1,2,3,4,5,6\}\), \(E=\{12,23,34,45,56\}\), and begin with the empty matching. Process possible roots in the order \(1,2,3,4,5,6\). Each search below finds an augmenting path consisting of a single edge.
| Search | Queue and discovery | Matching after augmentation |
|---|---|---|
| Root \(1\) | \([1]\); scan \(1\), reach free \(2\) | \(\{12\}\) |
| Root \(3\) | \([3]\); scan \(3\), reach free \(4\) | \(\{12,34\}\) |
| Root \(5\) | \([5]\); scan \(5\), reach free \(6\) | \(\{12,34,56\}\) |
Roots \(2,4,6\) are skipped when considered because they are already matched. The final matching has size \(3\). Check: a matching on six vertices can contain at most \(\lfloor 6/2\rfloor=3\) edges, since each matching edge uses two distinct vertices. The constructed matching reaches this bound, so it is maximum. This run uses three successful searches; in general there can be at most \(\lfloor n/2\rfloor\) successful augmentations because each increases the matching size by one and no matching has more than \(\lfloor n/2\rfloor\) edges.
Repeated Searches, Termination and a Common Pitfall
Each successful augmentation increases the size of the matching by exactly one, so there can be at most \(\lfloor n/2\rfloor\) successful augmentations, even if an implementation makes additional unsuccessful search attempts. In the root-sweep implementation analyzed above, there are at most \(n\) attempts altogether. The earlier material on augmenting paths and Edmonds’ blossom search establishes why a complete search procedure detects an augmenting path when one exists; the search is repeated until the root sweep is complete. The running-time analysis counts this repetition, rather than treating the first search as the whole algorithm.
Common pitfall: counting only one search. It is incorrect to conclude that the whole run takes \(O(n^2)\) just because one search scans at most \(n\) queue vertices and \(n\) possible neighbors per vertex. That calculation gives \(n\cdot n=n^2\) for one search. With at most \(n\) root attempts, the full bound is \(n\cdot n^2=n^3\). Contractions do not change the conclusion: their parent tracing and base updates have already been included in the \(O(n^2)\) per-search bound.
The useful lesson is to separate the costs by level: scanning and contracting within one search, then repeating searches across the run. The queue controls how often vertices are processed; parent links and bases make blossom handling possible; and the bound on the number of root attempts turns the per-search cost into a polynomial bound for the complete matching algorithm.
Check Your Understanding
Use the operation counts and the small-graph traces to check your understanding.
- Why does scanning all possible neighbors of each queued vertex take at most \(n^2\) time during one search?
- What information do parent links and base labels record, respectively?
- In the blossom example, list the three edges of the odd cycle and identify its base.
- Why can there be at most \(\lfloor n/2\rfloor\) successful augmentations?
- For the adjacency-matrix implementation, combine the per-search bound with the maximum number of search attempts to obtain the total running-time bound.