A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs

摘要

We give an O(n~(7/5) log(nC)) time algorithm to compute a minimum-cost maximum cardinality matching (optimal matching) in K_h-minor free graphs with h = O(1) and integer edge weights having magnitude at most C. This improves upon the O(n~(10/7) log C) algorithm of Cohen. [SODA 2017] and the O(n~(3/2) log(nC)) algorithm of Gabow and Tarjan [SIAM J. Comput. 1989]. For a graph with m edges and n vertices, the well-known Hungarian Algorithm computes a shortest augmenting path in each phase in O(m) time, yielding an optimal matching in O(mn) time. The Gabow-Tarjan [SIAM J. Comput. 1989] algorithm computes, in each phase, a maximal set of vertex-disjoint shortest augmenting paths (for appropriately defined costs) in O(m) time. This reduces the number of phases from n to O(√n) and the total execution time to O(m√n). To obtain our speed-up, we relax the conditions on the augmenting paths and iteratively compute,, in each phase, a set of carefully selected augmenting paths that are not restricted to be shortest or vertex-disjoint. As a result, our algorithm computes substantially more augmenting paths in each phase, reducing the number of phases from O(√n) to O(n~(2/5)). By using small vertex separators, the execution of each phase takes O(m) time on average. For planar graphs, we combine our algorithm with efficient shortest path data structures to obtain a minimum-cost perfect matching in O(n~(6/5) log (nC)) time. This improves upon the recent O(n~(4/3) log (nC)) time algorithm by Asathulla. [SODA 2018].