2019/03/25 by Lahn, Nathaniel, Raghvendra, Sharath
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1903.10445
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∪ 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 O( m(√(w)+ √(r)+(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 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 O(n4/3/ε4) time algorithm to compute an ε-approximate bottleneck matching of A,B⊂ℝ2 and an \frac1εO(d)n1+(d-1)/(2d-1)polylog n time algorithm for computing ε-approximate bottleneck matching in d-dimensions. All previous algorithms take Ω(n3/2) time. Given any graph G(A ∪ 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 O(mn^\fracδ1+δ) time improving upon the O(m√(n)) time taken by the HK-Algorithm.