Shared-Memory Parallel Edmonds Blossom Algorithm for Maximum Cardinality Matching in General Graphs

Area of Science:

• Computer Science
• Graph Theory
• Algorithm Optimization

Background:

• The Edmonds Blossom algorithm is a fundamental method for finding maximum matchings in general graphs.
• Existing implementations using depth-first search are inherently serial and can be computationally intensive.
• There is a need for faster and more efficient algorithms for graph matching, especially for large and complex networks.

Purpose of the Study:

• To develop a faster, parallelized implementation of the Edmonds Blossom algorithm.
• To investigate the performance gains achievable through code streamlining and parallelization techniques.
• To evaluate the algorithm's effectiveness on different types of graphs, including random and real-world networks.

Main Methods:

• Implemented the Edmonds Blossom algorithm using a streamlined, serial approach.
• Introduced parallelism by extracting computations across algorithm iterations using coarse-grain locking.
• Tested the optimized algorithm on random regular graphs and real-world graphs with varying densities and community structures.

Main Results:

• The streamlined serial implementation was 3-5 times faster than previous general graph matching codes.
• Parallelization with coarse-grain locking achieved a four-fold runtime reduction on random regular graphs and a two-fold reduction on real-world graphs.
• Sparse graphs with community structures showed a three-fold slowdown with eight threads, but this was overcome by marginal speedups on graphs with an average degree greater than four.

Conclusions:

• The parallel coarse-grain locking implementation of the Edmonds Blossom algorithm demonstrates significant performance improvements.
• This approach is effective for extracting parallelism from augmenting-path-based algorithms.
• The findings suggest that this parallel implementation may be suitable for similar graph-based algorithms and complex network analysis.