Maximum Cardinality Bipartite Matching

Application Description

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.

Algorithm

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 [1] 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 [1] 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.

[1] K. Mehlhorn and S. Naeher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, 1999.

Data Structures

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.

Performance

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

Figure 3: Execution time.
Figure 4: Self-relative Speedup.


Machine Description

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.