Faster shortest path method solves advanced network problems
A Shortest Augmenting Path Algorithm for Linear Matroid Parity
Data Structures and Algorithms
Summary
Finding the best way to pair items in complex systems can be very hard. The authors built a faster algorithm for a specific pairing problem called linear matroid parity, which generalizes important tasks like matching in networks. Their new method combines ideas from earlier algorithms with fresh math insights to speed up the process. This marks the first time a shortest augmenting path approach was successfully applied to this problem, improving known speed limits.
What this means in practice
- •For network engineers: Optimize complex network pairings faster in communications or data routing by applying improved linear matroid parity algorithms.
- •For algorithm engineers: Develop efficient software for combinatorial optimization problems in scheduling and resource allocation leveraging faster matroid parity methods.
Authors
Kou Hamada, Satoru Iwata
Abstract
The matroid parity problem serves as a fundamental framework that generalizes both graph matching and matroid intersection. Although the general version is intractable, Lovász (1981) developed a polynomial-time algorithm for the linear matroid parity problem, assuming the availability of matrix representations. Subsequently, Gabow and Stallmann (1986) presented an augmenting path algorithm, which has long been recognized as one of the fastest deterministic algorithms. Since shortest augmenting paths improved algorithms for graph matching (Micali & Vazirani, 1980) and linear matroid intersection (Cunningham, 1986), extending these techniques to linear matroid parity appears to be a natural progression. However, such an algorithm has remained elusive for four decades. In this paper, we present the first shortest augmenting path algorithm for linear matroid parity. Our approach synthesizes the augmenting path algorithm of Gabow and Stallmann with the synchronized blossom formation of the Micali$\unicode{8211}$Vazirani framework. Our key technical contributions are threefold: (i) a linear-algebraic argument that bounds the lengths of shortest augmenting paths for linear matroid parity, which generalizes Cunningham's bound for linear matroid intersection; (ii) an a priori characterization of shortest search paths through lower bounds on their lengths; and (iii) an extension of the structural properties for graph matching established by Izumi, Kitamura, and Yamaguchi (2025) to the linear matroid parity setting. Our algorithm deterministically solves the linear matroid parity problem in ${\rm O}(nr^2\log r)$ time, where $n$ is the ground set size and $r$ is the matroid rank. By incorporating fast matrix multiplication, this complexity can be further reduced to ${\rm O}(nr^2)$. These results improve upon the long-standing deterministic bounds of ${\rm O}(nr^3)$ and ${\rm O}(nr^ω)$.