A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings

We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(Acup B,E) with edge weights of 0 or 1. Let w ≤ n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in tildeO( m(√w+ √r+fracwrn)) time. When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in O(m√n) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sub-linear in n and wr=O(nγ) for γ < 3/2, then we can compute maximum cardinality matching in G in o(m√n) time. Using our algorithm, we obtain a new tildeO(n4/3/varepsilon4) time algorithm to compute an varepsilon-approximate bottleneck matching of A,Bsubsetℝ2 and an frac1varepsilonO(d)n^1+fracd-12d-1polylog n time algorithm for computing varepsilon-approximate bottleneck matching in d-dimensions. All previous algorithms take Omega(n3/2) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size |V'|δ, for δ∈ [1/2,1), we can apply our algorithm to compute a maximum matching in tildeO(mn^fracδ1+δ) time improving upon the O(m√n) time taken by the HK-Algorithm.