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

arXiv: https://arxiv.org/abs/1903.10445 · HTML: https://mlsanity.com/paper/1903.10445/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2019.

## Built on by (most cited first, 2 of 2)

- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [A Push-Relabel Based Additive Approximation for Optimal Transport](https://mlsanity.com/paper/2203.03732/) (2022)

## Abstract (arXiv)

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.