A Faster Maximum Cardinality Matching Algorithm with Applications in Machine Learning

Abstract

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 O(n^3/2) time.~We use O() to suppress poly-logarithmic terms in the complexity. 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 O(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.

Tasks

Reproductions