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

Nathaniel Lahn, Sharath Raghvendra

Abstract

We present an $\tilde{O}(n^{7/5} \log (nC))$-time algorithm to compute a minimum-cost maximum cardinality matching in $K_h$-minor free graphs with integer edge weights of magnitude at most $C$. This improves upon the previous $\tilde{O}(n^{10/7}\log{C})$ and $O(n^{3/2}\log (nC))$ benchmarks. By relaxing traditional constraints on augmenting paths—specifically that they be shortest and vertex-disjoint—we reduce the number of required phases from $O(\sqrt{n})$ to $O(n^{2/5})$. For planar graphs, our algorithm achieves a complexity of $\tilde{O}(n^{6/5} \log{(nC)})$, setting a new state-of-the-art bound.

Introduction

Bipartite matching is a fundamental problem in combinatorial optimization: given two sets of nodes (e.g., workers and tasks) and weighted edges, find the set of pairs that maximizes matches while minimizing total cost. While classic algorithms like the Hungarian Method or Gabow-Tarjan typically run in $O(m\sqrt{n})$ time—effectively $O(n^{1.5})$ for sparse graphs—this research breaks that barrier for "minor-free" graphs, a broad category that includes planar graphs.

Methodology

The algorithm, termed the AKLR-Algorithm, employs a "divide and conquer" strategy combined with a relaxed search for augmenting paths. It is structured around three core innovations:

1. Graph Compression via r-Clustering

The graph is partitioned into edge-disjoint subgraphs called $r$-clusters. Each cluster has a limited number of boundary vertices shared with other pieces. This allows the algorithm to operate on a compressed graph $H$, where edges represent shortest paths within these clusters, significantly reducing the search space for augmenting paths.

2. The FASTMATCH Procedure

Traditional algorithms (like Hopcroft-Karp) find a maximal set of vertex-disjoint shortest augmenting paths. The FASTMATCH procedure deviates by allowing paths that are neither strictly shortest nor strictly vertex-disjoint. By using a modified Depth-First Search on an "admissible" graph that allows for "slack" in edge costs, the algorithm discovers substantially more augmenting paths per phase.

Illustration of the FASTMATCH procedure's path augmentation logic, showing how paths are selected and augmented within the compressed graph structure.

3. Scaling and Complexity

To handle edge weights, the algorithm uses a bit-scaling framework, solving for the most significant bits first and iteratively refining the solution. This approach, combined with aggressive dual weight updates for free vertices, ensures convergence in significantly fewer phases than traditional scaling methods.

Summary of the AKLR-Algorithm and its phase-based complexity, highlighting the time requirements for preprocessing and search iterations.

Key Results

The paper establishes new theoretical bounds for weighted bipartite matching in structured graphs:

  • Minor-Free Graphs: The algorithm achieves a running time of $\tilde{O}(n^{7/5} \log(nC))$, a significant improvement over the previous best of $\tilde{O}(n^{10/7} \log C)$.
  • Planar Graphs: By integrating specialized planar shortest-path data structures, the bound drops to $\tilde{O}(n^{6/5} \log(nC))$.
  • Phase Reduction: The total number of phases required to reach an optimal matching is reduced from the standard $O(\sqrt{n})$ to $O(n^{2/5})$.

Conclusion

By relaxing the strict requirements for augmenting paths and exploiting the separator properties of minor-free graphs, this algorithm provides a major theoretical speedup. While the implementation involves complex data structures, the reduction in phase complexity represents a significant step toward near-linear time matching in sparse, structured graphs.

Summary updated

Abstract

We give an $\tilde{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 $\tilde{O}(n^{10/7}\log{C})$ 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(\sqrt{n})$ and the total execution time to $O(m\sqrt{n})$. 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(\sqrt{n})$ to $O(n^{2/5})$. By using small vertex separators, the execution of each phase takes $\tilde{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 $\tilde{O}(n^{6/5} \log{(nC)})$ time. This improves upon the recent $\tilde{O}(n^{4/3}\log{(nC)})$ time algorithm by Asathulla et al. [SODA 2018].
BibTeX
@inproceedings{lahn2019faster,
  author = {Nathaniel Lahn and Sharath Raghvendra},
  title = {{A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs}},
  booktitle = {SODA},
  year = {2019},
  url = {https://openreview.net/forum?id=EX3G1VcByvq},
}
Figure