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(A\cup B,E)$ with edge weights of $0$ or $1$. Let $w\le 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 $\mathcal{O}(r)$ vertices and $\mathcal{O}(mr\mathrm{/}n)$ edges. We present an algorithm to compute a maximum cardinality matching in $G$ in $\tilde{$\mathcal{O}$}( m(\sqrt{w}+ \sqrt{r}+\frac{wr}{n}))$ 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 $\mathcal{O}(m\sqrt{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=\mathcal{O}(n^{\gamma })$ for $\gamma <3\mathrm{/}2$, then we can compute maximum cardinality matching in $G$ in $o(m\sqrt{n})$ time. Using our algorithm, we obtain a new $\tilde{\mathcal{O}}(n^{4\mathrm{/}3}\mathrm{/}{\epsilon }^4)$ time algorithm to compute an $\epsilon$-approximate bottleneck matching of $A,B\subset {\mathbb{R}}^2$ and an $\frac{1}{\varepsilon^{$\mathcal{O}$(d)}}n^{1+\frac{d-1}{2d-1}}$\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$\log n$timealgorithmforcomputing$\varepsilon$-approximate bottleneck matching in $d$-dimensions. All previous algorithms take $\mathrm{\Omega }(n^{3\mathrm{/}2})$ time. Given any graph $G(A\cup B,E)$ that has an easily computable balanced vertex separator for every subgraph $G^{\mathrm{\prime }}(V^{\mathrm{\prime }},E^{\mathrm{\prime }})$ of size $\mathrm{\mid }{V}^{\mathrm{\prime }}{\mathrm{\mid }}^{\delta }$, for $\delta \in [1\mathrm{/}2,1)$, we can apply our algorithm to compute a maximum matching in $\tilde{\mathcal{O}}(m{n}^{\frac{\delta }{1+\delta }})$ time improving upon the $\mathcal{O}(m\sqrt{n})$ time taken by the HK-Algorithm.