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.
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.
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