Maximum Cardinality Bipartite Matching
Given a graph G, a matching M is a subset of edges where no two edges share an endpoint. The cardinality |M| of M is the number of edges in M . Given an unweighted bipartite graph G = (V, E) V = (A, B), the maximum cardinality bipartite matching problem is to find a matching with maximum cardinality.
Algorithms to solve this problem try to extend existing matchings by finding augmenting paths. When there are no more augmenting paths, the matching is a maximum matching.
The Ford-Fulkerson algorithm  visits each node in A trying to find an augmenting path at each. It has complexity O(|V||E|). The Alt-Blum-Mehlhorn-Paul (ABMP) algorithm  tries to find the shortest augmenting path first. After all the augmenting paths of less than a particular length are found or the number of unmatched nodes is reduced to a particular size, the algorithm applies the Ford-Fulkerson algorithm to complete the matching. The ABMP algorithm has complexity O(|E|sqrt(|V|)).
This benchmark implements the Alt-Blum-Mehlhorn-Paul algorithm.
 K. Mehlhorn and S. Naeher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, 1999.
There are two key data structures used in this algorithm:
- Priority Scheduler
- The ABMP algorithm uses priority on tasks to find the shortest augmenting paths first.
- Directed Graph
- The algorithm successively reads and updates a graph.
Figure 3 and Figure 4 show the execution time in seconds and self-relative speedup (speedup with respect to the single thread performance), respectively, of this algorithm
Performance numbers are collected on a 4 package (14 cores per package) Intel(R) Xeon(R) Gold 5120 CPU machine at 2.20GHz from 1 thread to 56 threads in increments of 7 threads. The machine has 192GB of RAM. The operating system is CentOS Linux release 7.5.1804. All runs of the Galois benchmarks used gcc/g++ 7.2 to compile.