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

Nathaniel Lahn, Sharath Raghvendra

TL;DR

This paper introduces a breakthrough algorithm for finding the minimum-cost maximum matching in bipartite graphs that are "minor-free" (a broad category including planar graphs). By relaxing the traditional requirement that augmenting paths must be the absolute shortest and vertex-disjoint, the authors achieve a significant speedup, reaching a running time of $\tilde{O}(n^{7/5} \log(nC))$ for minor-free graphs and $\tilde{O}(n^{6/5} \log(nC))$ for planar graphs.

What Problem Does This Paper Address?

Bipartite matching is a cornerstone of combinatorial optimization: given two sets of nodes (like workers and tasks) and weighted edges between them, find the set of pairs that maximizes the number of matches while minimizing total cost.

While we’ve had efficient algorithms for decades, the "holy grail" in theoretical computer science is pushing these bounds closer to linear time, especially for sparse graphs. For a graph with $n$ vertices and $m$ edges, classic algorithms like the Hungarian Method or Gabow-Tarjan typically run in $O(m\sqrt{n})$ time. In sparse graphs where $m \approx n$, this is $O(n^{1.5})$. This paper aims to break that $n^{1.5}$ barrier for specific, structurally restricted graphs—specifically "minor-free" graphs, which are graphs that do not contain a specific forbidden structure (K-minors).

Methods

The authors employ a "divide and conquer" strategy combined with a relaxed search for augmenting paths.

  1. $r$-Clustering: The graph is partitioned into edge-disjoint pieces called an $r$-clustering. Each piece has a limited number of "boundary vertices" (nodes shared with other pieces). This allows the algorithm to work on a "compressed" version of the graph ($H$) where edges represent shortest paths within the pieces.
  2. Bit-Scaling: To handle edge weights, the algorithm uses a scaling framework. It solves the problem for the most significant bits of the costs first, then iteratively refines the solution as more bits are considered.
  3. The FASTMATCH Procedure: This is the core innovation. Traditional algorithms (like Hopcroft-Karp) find a maximal set of vertex-disjoint shortest augmenting paths in each phase. This paper deviates by allowing paths that aren't necessarily the shortest and aren't strictly vertex-disjoint.
  4. DFS-style Search: Instead of a standard BFS, they use a modified Depth-First Search on an "admissible" graph that allows for some "slack" in edge costs. This allows the algorithm to discover and augment many more paths in a single phase, reducing the total number of phases from $O(\sqrt{n})$ to $O(n^{2/5})$.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets or benchmarks. Instead, it provides rigorous mathematical proofs of time complexity for specific graph classes:

  • $K_h$-minor free graphs: A generalization of planar graphs.
  • Planar graphs: Graphs that can be drawn on a plane without edges crossing.

Key Insights and Ideas

  • Relaxation is Faster: The "aha moment" is realizing that being too strict about finding the absolute shortest path is computationally expensive. By allowing paths with a small amount of "slack" (error), you can find many more paths quickly.
  • Vertex Reuse: Unlike the GT or HK algorithms, which discard visited vertices during a phase, this algorithm allows vertices to be revisited. While this sounds like it would slow things down, the authors prove that the total number of revisits is bounded by the $r$-clustering structure.
  • Aggressive Dual Weight Updates: The algorithm aggressively increases the "dual weights" (a mathematical tool used to track progress toward optimality) of free vertices. This forces the algorithm to converge much faster than traditional scaling methods.

Key Results

The paper achieves new state-of-the-art theoretical bounds for weighted bipartite matching:

  • Minor-Free Graphs: The algorithm runs in $\tilde{O}(n^{7/5} \log(nC))$ time. This is a significant improvement over the previous best of $\tilde{O}(n^{10/7} \log C)$ by Cohen et al. (2017).
  • Planar Graphs: By integrating with specialized planar shortest-path data structures, the bound drops to $\tilde{O}(n^{6/5} \log(nC))$. This beats the previous record of $\tilde{O}(n^{4/3} \log(nC))$ set just months prior.
  • Phase Reduction: The number of phases required to reach an optimal matching is reduced from the standard $O(\sqrt{n})$ to $O(n^{2/5})$.

Limitations and Future Work

  • Structural Dependence: The speedup relies heavily on the graph having small separators (the $r$-clustering). It does not improve the $O(n^{1.5})$ bound for general, dense graphs.
  • Complexity of Implementation: The algorithm is theoretically elegant but involves complex data structures (like Monge-property range searching for the planar case), which might make it challenging to implement efficiently in practice compared to simpler heuristics.
  • Open Questions: The authors suggest two main paths forward:
  • Can the CONSTRUCT procedure for minor-free graphs be improved from $O(r^{1.5})$ to $O(r)$?
  • Can we bridge the gap between this $O(n^{1.2})$ weighted algorithm and the $O(n \text{ polylog } n)$ algorithms that exist for unweighted planar matching?

Summary updated

Abstract

We give an Õ(n7/5 log(nC)) time1 algorithm to compute a minimum-cost maximum cardinality matching (optimal matching) in Kh-minor free graphs with h = O(1) and integer edge weights having magnitude at most C. This improves upon the Õ(n10/7 log C) algorithm of Cohen et al‥ [SODA 2017] and the O(n3/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 and the total execution time to . 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 to O(n2/5). By using small vertex separators, the execution of each phase takes Õ(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 Õ(n6/5 log (nC)) time. This improves upon the recent Õ(n4/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},
}

Loading related content...

Figure