We describe an implementation and experimental evaluation of Blum's maximum matching algorithm in general graphs. Blum's algorithm finds augmenting paths in general graphs without explicitly analyzing blossoms. Although there are many implementations and performance studies of Edmonds' blossom algorithm and its variants, we are not aware of any implementation of Blum's approach. We compare three implementations: Blossom I, Blossom V, and Blum's modified depth-first search (MDFS). We extend Blum's algorithm with a preprocessing step that computes an initial random matching. This significantly reduces the number of augmenting path searches. We prepared a Java implementation of MDFS. We describe how to handle some cases that are not fully discussed in Blum's article. We created a unified experimental framework for testing the algorithms on random graphs, geometric graphs, complete graphs, DIMACS benchmark graphs, and overlapping cycles. Our experiments show that Blossom V is always faster than Blossom I and very eficient on all inputs. Blum's algorithm with preprocessing competes with Blossom V in several classes of graphs and outperforms it in some cases, which confirms the resilience of MDFS if properly initialized. These results suggest that preprocessing makes reachability-based algorithms a good alternative to blossom algorithms.
The problem of computing a maximum cardinality matching in general undirected graphs is a
fundamental problem in graph theory and combinatorial optimization. A matching is a set of edges such that
no two edges share a common vertex. A matching is maximum if it contains the largest possible number
of such edges. The theoretical foundation for modern algorithms is Berge’s theorem [
In bipartite graphs, augmenting paths can be found by a BFS or DFS like method, leading to eficient
algorithms such as the Hopcroft–Karp algorithm for maximum matching in (√) time [
This challenge was overcome by Edmonds [
This bound is maintained in initial implementations like Blossom I [
Blum suggested an efective alternative solution using graph transformation and reachability [
In this paper, we present an experimental evaluation of three algorithms for maximum cardinality
matching:
• Blossom I, with a public domain Java implementation; [
We compare their performance on a range of graph instances and analyze the efect of providing
initial matching. We also identify some cases that are not completely covered by the MDFS in [
Our key contributions are the following:
• A unified experimental framework in Java for comparing Blossom I, Blossom V, and MDFS on
unweighted graphs.
• An MDFS algorithm implementation of Blum’s algorithm with practical robustness enhancements
for specific cases that are not completely covered in [
The remainder of this paper is structured as follows. Section 2 provides background and necessary algorithmic concepts, and our extension of MDFS. Section 3 presents the experimental setup and comparative results. Section 4 concludes with a discussion and future work.
We use publicly available Java implementations of Blossom I and Blossom V to contrast classical
blossom-based algorithms in this paper. For Blum’s algorithm, we used the reformulation in [
The remainder of this section gives the basic definitions used in MDFS, and then describes in detail the specific cases we discovered and how we corrected them.
Let = (, ) be an undirected, and unweighted graph where is the set of vertices and is the set of edges ⊆ {{ , } | , ∈ , ̸= }. A bipartite graph is a graph whose vertex set can be partitioned into two disjoint sets and , and whose edges join vertices of to those of . A matching ⊆ is a set of edges such that no two edges in share a common vertex. A vertex is matched if it is incident on an edge in ; otherwise, it is free.
An augmenting path is an elementary path in such that it starts and ends at free vertices and keeps alternating between non-matching edges and matching edges.
Following Berge’s theorem [
Blum’s algorithm formulates the maximum matching problem as a reachability problem in an induced directed bipartite graph ′, constructed from the given undirected graph = (, ), and a given matching ⊆ .
For each vertex ∈ , two vertices and are constructed, efectively making a copy of the set of vertices and generating a bipartition ∪ . The key concept utilized in this formulation is that of the strongly simple path, a directed path in ′ with the following conditions: 1. Has no pair of vertices , (having the same original vertex ). 2. Is simple (no repeated vertices). 3. Follows edge direction rules expressing the existing matching status.
For each undirected edge {, } ∈ , the transformation adds directed edges to ′ depending on whether the edge is part of the matching : • If {, } ∈/ , two forward edges are added: → and → . These represent steps along unmatched edges and are directed from to . • If {, } ∈ , two backward edges are added: → and → . These represent matched edges and are directed from to .
This construction ensures that traversing the → edges corresponds to traversing the existing
matching, and that the → edges represent candidate moves toward establishing new matches. A
Modified Depth-First Search (MDFS) on ′ is started from a source vertex connecting all free vertices
of side , and attempts to find a strongly simple path to a sink vertex connecting all free vertices of
side . Upon finding such a path, it translates to an alternating path in the original graph that can be
applied to augment the existing matching. In each augmentation that succeeds, the size of the matching
is incremented by one [
In practice, the edges traversed by MDFS can be classified into five categories: tree edges, forward
edges, cross edges, back edges, and weak back edges [
While implementing the algorithm, whenever a vertex is popped from the stack, the algorithm looks for reachable vertices from where it can further build a valid strongly simple path. These vertices are then stored in the set: := { ∈ ′ | ∃ path = (, , ) ∧ ∈/ ∧ PUSH() has never been performed ∧ POP() has been performed }
According to Blum’s [
We also rely on the following data structures introduced by Blum [
:= { ∈ ′ | (, ) is a weak back edge} := { ∈ ′ | (, ) is a cross, forward, or back edge}
:= { ∈ ′ | = previously}
We define the expanded MDFS-tree as the tree obtained from the constructed MDFS-tree by adding all forward, back, cross, and weak back edges, together with every extensible edge. To determine the vertices in when is popped, a backward search is performed on . This search is carried out using a standard graph traversal, such as depth-first search, starting from vertex and exploring the considered edges in reverse until is reached.
To support the reconstruction of a strongly simple path when reaching , the algorithm maintains a variable that records the most recent non-tree edge terminating at vertex .
While implementing Blum’s MDFS algorithm [
When the traversal encounters a weak back edge (, ) – classified as Case 2.2.i – the original algorithm does not perform any action. Specifically, it does not update and , such that there is a path = , , and ∈/ has been found by the MDFS, even though the edge may play a structurally important role in the reconstruction of a strongly simple path.
Updating the value of is essential for correctly reconstructing the augmenting path from to . Without this update, the algorithm may terminate prematurely or fail to identify an existing augmenting path, violating its correctness guarantee in these specific configurations.
To solve this issue, whenever the algorithm encounters a weak back edge (, ), we add to . This operation ensures that structurally significant relationships are preserved for future use. In order to improve the correctness and eficiency of this operation, we selectively choose which vertices are added based on the traversal history.
Specifically, we allow to be added to under either of the following two situations: • has not yet been visited by MDFS • was pushed onto the stack before (c) Tree built by Blum’s MDFS. Edges to green vertices represent weak back edges from Case 2.2.ii, edges to purple vertices represent a forward or cross edge (Case 2.3.i) used to connect an extensible vertex via an extensible edge (d) Corrected tree with our fix. Edges to green vertices represent weak back edges from Case 2.2.ii, edges to blue vertices correspond to Case 2.2.i, edges to purple vertices represent a forward or cross edge (Case 2.3.i) used to connect an extensible vertex via an extensible edge
After the execution of ( ), there is a backward traversal of the current expanded tree from the vertex along edges in the opposite direction. Whenever a vertex is visited through this traversal, it is added to the set , but no value is given to .
The behavior of this case is illustrated in Figure 1. The original graph , along with its current matching, is presented in Figure 1a.
The tree constructed by Blum’s original MDFS is presented in Figure 1c, When is found then 8 = (9 , 7), 9 = (8 , 7), 4 = (5 , 3), 5 = (4 , 3), 6 = (8 , 3). To reconstruct the strongly simple path from to , we start with the last vertex and follow the parents in . We obtain the path segment 3 → 2 → 10 → .
At this point, the parent of 3 in is an extensible vertex 1 [9], meaning it was added via Case 2.3.i, using an extensible edge (1, 3)[9]. Now we have 9 = (8, 7). So we reconstruct the path from 9 to 8: 9 → 8, next we search for 7 . Since 7 is undefined, the reconstruction process fails at this point.
In contrast, our modified version of the algorithm builds the tree shown in Figure 1d. First we pop 7, and then we get 8 = (9, 7), 9 = (8, 7), next we pop 4, and then we get 6 = (7, 4), 7 = (6, 4), next we pop 3, and we get 4 = (5, 3), 5 = (4, 3), after that we find . The reconstruction of the strongly simple path from to starts with the last vertex , and it follows the parents in . It obtains the path segment 3 → 2 → 10 → .
At this point, the parent of 3 in is an extensible vertex 1 [9], meaning it was added via Case 2.3.i, using an extensible edge (1, 3)[9]. Now we have 9 = (8, 7). We reconstruct the path from 9 to 8: 9 → 8. Then we have 7 = (6, 4), so we reconstruct path from 7 to 6: 7 → 6. Then we have 4 = (5, 3), so we reconstruct path from 4 to 5: 4 → 5. Then we get 3, so we continue from 1: → 1. The strongly simple path will be:
→ 1 → 9 → 8 → 7 → 6 → 4 → 5 → 3 → 2 → 10 →
The outcome is shown in Figure 1b, where the algorithm correctly finds an augmenting path and increases the cardinality of the matching by one. The example confirms the need to handle weak back edges diferently to ensure MDFS correctness for any case.
When the traversal encounters a forward edge (, ) of Case 2.3.i with = ∅, the original algorithm does nothing. This may result in the absence of valid path segments and, therefore, incomplete augmentation or reconstruction.
To address this issue, the algorithm records each forward or cross edge when = ∅ and adds it to a new set WC:
:= { ∈ ′ | (, ) is a forward or cross edge and = ∅ }
To improve the eficiency of this operation, we include in subject to the condition that either of the following holds in the extended tree: • is a parent of • and are not on the same path
The behavior of this case is illustrated in Figure 2. The original graph , along with its current matching, is presented in Figure 2a.
The tree constructed by Blum’s original MDFS is presented in Figure 2c, When is found, then 10 = (11, 9), 11 = (10, 9), 6 = (7, 5), 7 = (6, 5), 5 = (4, 3), 4 = (7, 3), 8 = (9, 4). To reconstruct the strongly simple path from to , we start with the last vertex and follow the parents in . We obtain the path segment 3 → 2 → 12 → .
At this point, the parent of 3 is an extensible vertex 1 [11], meaning it was added via Case 2.3.i, using an extensible edge (1, 3)[11]. Now we have 11 = (10, 9), so we reconstruct path from 11 to 10: 11 → 10, next we search for 9 . Since 9 is undefined, the reconstruction process fails at this point.
In contrast, our modified version of the algorithm builds as shown in Figure 2d. First we pop 9, and then we get 10 = (11, 9), 11 = (10, 9). Next we pop 5, and then we get 6 = (7, 5), 7 = (6, 5). Next we pop 3, and we get 4 = (7, 3), 5 = (4, 3), 8 = (9, 4), 9 = (8, 6). After that, we find . The reconstruction of the strongly simple (c) Tree built by Blum’s MDFS, edges to green vertices represent weak back edges, edges to red vertices represent back, cross, or forward edges, edges to purple vertices represent a forward or cross edge (Case 2.3.i) used to connect an extensible vertex via an extensible edge. (d) Corrected tree with our fix. Edges to green vertices represent weak back edges, edges to red vertices represent back, cross, or forward edges. Edges to blue vertices correspond to Case 2.3.i when = ∅. Edges to purple vertices represent a forward or cross edge (Case 2.3.i) used to connect an extensible vertex via an extensible edge path from to starts with the last vertex and follows the parents in . It obtains the path segment 3 → 2 → 12 → .
At this point,the parent of 3 is an extensible vertex 1 [11], meaning it was added via Case 2.3.i, using an extensible edge (1 , 3)[11]. Now we have 11 = (10 , 9), so we reconstruct path from 11 to 10 : 11 → 10 , then we have 9 = (8 , 6), so we reconstruct path from 9 to 8 : 9 → 8 . Then we have 6 = (7 , 5), so we reconstruct path from 6 to 7 : 6 → 7 . Next we have 5 = (4 , 3), so we reconstruct path from 5 to 4 : 5 → 4 . Then we get 3, so we continue from 1 : → 1 Finally, the strongly simple path will be:
→ 1 → 11 → 10 → 9 → 8 → 6 → 7 → 5 → 4 → 3 → 2 → 12 → The outcome is shown in Figure 2b, where the algorithm correctly finds an augmenting path and increases the cardinality of the matching by one. The example confirms the need to handle forward or cross edges diferently when = ∅ to ensure MDFS correctness for any case.
In this section, we present a comparative analysis of the performance of three maximum matching algorithms: Blossom I, Blossom V, and Blum’s MDFS algorithm. Our experiments are divided into two stages. In the first stage, we compare Blossom I and Blossom V using a diverse set of unweighted, undirected graphs. This comparison highlights the efect of algorithmic optimizations and internal data structure choices, such as queue-based event handling, on runtime performance.
In the second stage, we evaluate Blum’s MDFS algorithm against Blossom V. We test two versions of
Blum’s algorithm: one running from scratch, and the other initialized with a random greedy matching
(denoted as Blum Preparatory), which processes the edges in a random order and adds the edge to
the matching if both end vertices are unmatched. This variation allows us to assess how providing
an initial matching afects the performance and convergence speed of MDFS. The initial matching is
applied only to MDFS, as Blossom V already employs a greedy initialization [
All the experiments were performed on a computer with an Intel(R) Core(TM) i7-7700HQ CPU (2.80GHz), 16GB RAM, under Windows 10 (64-bit). The code was written in Java and executed under the NetBeans 20.0 integrated development environment.
The Java runtime environment was Java 21.0.2 (LTS), provided by Oracle Corporation, under the Java HotSpot™ 64-Bit Server VM (version 21.0.2+13-LTS-58). Run times were gathered with System.currentTimeMillis(), and we only counted the time taken in the core matching function. The construction of the bipartite graph and the initialization of the random matching were included in the time measurements, while I/O accesses and graph construction were excluded.
We evaluated the algorithms on eight distinct types of problem instances to ensure diversity in both structure and complexity. Several of these instance generators incorporate randomness; in such cases, we report the average runtime over independent runs using diferent random seeds. The value of is indicated in the figure captions. All graphs are described by their number of vertices , which are shown along the horizontal axes of the runtime plots.
Delaunay triangulations: We generated points at random with a uniform distribution in a 220 × 220
square and then computed the Delaunay triangulation of the point set. For constructing Delaunay
triangulations, we employed a Java procedure that conformed to the key ideas and geometric ideas of
Shewchuk’s 2D Delaunay triangulation algorithm [
Erdős-Rényi Random Graphs: We generated random graphs with vertices and edges by
randomly selecting pairs of distinct vertices. We examined two cases = 6 and = 80.
Complete Graphs: We also included full graphs in our set of benchmarks, where every graph has all
the possible edges between vertices. The number of edges in those graphs is = (2− 1) .
DIMACS Benchmark Graphs: We used families of examples from the First DIMACS Implementation
Challenge [
Each instance is parameterized by an integer , which determines the size and complexity of the generated graph.
Overlapping Cycles: For testing the resilience of the algorithms, we built our own generator that generates graphs composed of overlapping cycles of odd and even size. These instances are specifically designed in a way that would challenge matching algorithms to their limits by inserting complex structures such as nested and intersecting cycles. The presence of crossing odd-length cycles is hardest for blossom-based methods, while even-length cycles test the algorithm to detect and follow alternative paths. These are structurally dense test cases that put a strain on the limits of contraction, labeling, and path-reconstruction logic and reveal a lot about the correctness and performance of the algorithm in adversarial-like instances.
We compared Blossom I and Blossom V’s run-time behavior on several graph families, namely, Delaunay triangulations, random graphs, complete graphs, overlapping cycles, and instances of the DIMACS benchmarks. In all cases, Blossom V behaves uniformly better than Blossom I.
Figure 3 summarizes the results, where the running time is plotted on a logarithmic scale to clearly illustrate performance diferences of the algorithms. Blossom I exhibits explosive growth in running time with graph size, particularly for dense graphs. In contrast, Blossom V has reliable and eficient performance since it utilizes priority queues, optimized blossom management, and improved data structures.
This section compares the performance of three algorithms: Blossom V, Blum’s MDFS, and Blum Preparatory, a variant of MDFS that starts with an initial matching. Our goal is to assess both the raw performance and the practical implications of Blum’s avoidance of blossom shrinking, especially when combined with a random greedy initial matching. Figure 4 summarizes the results, where the running time is plotted on a logarithmic scale. Figure 4a shows the results for Delaunay triangulations. Here, the standard Blum code is consistently slower than both competitors. Nevertheless, Blum Preparatory performs much better and often outperforms Blossom V on instances of mid-to-large size. This result shows the strength of MDFS when combined with a precomputed matching.
On random graphs with = 6 (Figure 4b), Blossom V is always the fastest algorithm. While in random graphs with = 80 (Figure 4c), all algorithms perform reasonably well, but the preparatory version of Blum consistently tracks or slightly outperforms Blossom V, particularly as increases. This suggests that the combination of simplicity and a warm start is efective.
The results on complete graphs (Figure 4d) are more predictable. Blum Preparatory handles the complete graphs better overall.
The results on overlapping cycle instances are shown in Figure 4e. Here, the performance gap between Blum and Blum Preparatory is significant, demonstrating the burden of full search in blossom-heavy graphs. Blum Preparatory is very competitive with Blossom V.
Figures 4f to 4h show the results on DIMACS graphs. As sample cases, these are chosen to be challenging, with wild blossom production. These instances also represent worst-case scenarios for MDFS due to the existence of numerous alternative paths. Blossom V performs best on the hardcard graph instances, and Blum Preparatory is the fastest on the T and TT instances.
Summary: Blossom V has the best overall runtime for the most graph families. Blum Preparatory is the fastest on complete graphs, T, and TT instances of the DIMACS graphs. It is highly competitive in many structured graphs. It does not require blossom shrinking to beat or nearly match Blossom V. These results suggest that, in real-world scenarios where an approximation for a matching is known or is inexpensively computable, MDFS-based algorithms represent a good and clean alternative. (a) Delaunay triangulation graphs ( = 50) (c) Random graphs ( = 50 and = 80) (d) Complete graphs (e) Overlapping cycles ( = 50) (f) DIMACS hardcard graphs (g) DIMACS T graphs (h) DIMACS TT graphs
We gave a comparative analysis of the three maximum matching algorithms in unweighted, undirected graphs: Blossom I, Blossom V, and Blum’s MDFS algorithm, along with a version that initializes MDFS with a random greedy matching. We compared both theoretical and experimental diferences of performance over a large set of graph families: random graphs, geometric graphs, complete graphs, DIMACS benchmarks, and overlapping cycles.
The results show that Blossom V performs substantially better than Blossom I due to improved data structures and heuristics. More importantly, our results show that Blum Preparatory, due to not (a) Delaunay triangulations ( = 50) (c) Random graphs ( = 50 and = 80) (d) Complete graphs (e) Overlapping cycles ( = 50) (f) DIMACS hardcard graphs (g) DIMACS T graphs (h) DIMACS TT graphs being complex and blossom shrinking overhead free, can achieve highly competitive performance, even beating Blossom V in some cases, particularly for structured and sparse graphs. This confirms the practical applicability of reachability-based matching when given a good initial matching.
We implemented of Blum’s MDFS in Java and proposed some corrections for the previously found edge cases, rendering it correct and more versatile. Not only do these modifications enhance Blum’s algorithm for real-world applications, but they also shed light on how initialization and structural characteristics of the input graph afect the eficiency of matching.
In conclusion, the paper confirms the efectiveness of augmenting path algorithms and draws out the inner strength of other techniques like MDFS. Some avenues for research work may include exploring hybrid techniques, parallel algorithms, and expanding analysis to the dynamic, weighted graphs or maximum 2-matching problems.
During the preparation of this work, the author(s) used Grammarly solely for grammar and spelling correction. After using this tool, the author(s) carefully reviewed and edited the content as needed and take(s) full responsibility for the publication’s content.