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

DOI10.1137/1.9781611975482.36MaRDI QIDQ5236217zbMATH OpenOpenAlexFDO

Authors Nathaniel Adam Lahn, Sharath Raghvendra

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.04802

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: We give an $ildeO(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 $ildeO(n^{10/7}logC)$ algorithm of Cohen et al. [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 Hopcroft-Karp [SIAM J. Comput. 1973], and Gabow-Tarjan [SIAM J. Comput. 1989] algorithms compute, 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(sqrtn)$ and the total execution time to $O(msqrtn)$. In order 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(sqrtn)$ to $O(n^{2/5})$. By using small vertex separators, the execution of each phase takes $ildeO(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 $ildeO(n^{6/5}log(nC))$ time. This improves upon the recent $ildeO(n^{4/3}log(nC))$ time algorithm by Asathulla et al. [SODA 2018].

Recommendations

• A faster algorithm for minimum-cost bipartite perfect matching in planar graphs
• A faster algorithm for minimum-cost bipartite perfect matching in planar graphs
• scientific article; zbMATH DE number 2154963
• Finding all minimum-cost perfect matchings in Bipartite graphs
• A fast dynamic optimum algorithm for maximum matching in bipartite graphs
• Solving matching problems efficiently in bipartite graphs
• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• An efficient algorithm for the bipartite matching problem
• scientific article; zbMATH DE number 7651215
• A perfect matching algorithm for sparse bipartite graphs

Cited in

(7)

• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• Maximum matching in graphs with an excluded minor
• A faster algorithm for minimum-cost bipartite perfect matching in planar graphs
• A faster algorithm for minimum-cost bipartite perfect matching in planar graphs
• Min-Cost Flow in Unit-Capacity Planar Graphs
• A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time

This page was built for publication: A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236217)