A Faster Maximum Cardinality Matching Algorithm with Applications in Machine Learning

Maximum cardinality bipartite matching is an important graph optimization problem with several applications. For instance, maximum cardinality matching in a δ-disc graph can be used in the computation of the bottleneck matching as well as the ∞-Wasserstein and the Lévy-Prokhorov distances between probability distributions. For any point sets A, B ⊂ R 2 , the δ-disc graph is a bipartite graph formed by connecting every pair of points (a, b) ∈ A × B by an edge if the Euclidean distance between them is at most δ. Using the classical Hopcroft-Karp algorithm, a maximum-cardinality matching on any δ-disc graph can be found in Õ(n 3/2 ) time. 2 In this paper, we present a simplification of a recent algorithm (Lahn and Raghvendra, JoCG 2021) for the maximum cardinality matching problem and describe how a maximum cardinality matching in a δ-disc graph can be computed asymptotically faster than O(n 3/2 ) time for any moderately dense point set. As applications, we show that if A and B are point sets drawn uniformly at random from a unit square, an exact bottleneck matching can be computed in Õ(n 4/3 ) time. On the other hand, experiments suggest that the Hopcroft-Karp algorithm seems to take roughly Θ(n 3/2 ) time for this case. This translates to substantial improvements in execution time for larger inputs.