Graphic matroid parity solved faster than previous nm time barrier
Faster graphic matroid parity: Breaking the $nm$ time complexity barrier
Data Structures and Algorithms
Summary
The graphic matroid parity problem involves choosing pairs of edges in a graph so that their union forms a forest, which is a structure without cycles. This problem is tricky and generalizes other well-known graph problems like matching. Previous best algorithms ran in time proportional to the product of the number of vertices and pairs of edges, which could be slow. The authors developed a new randomized algorithm that runs faster, especially when the graph is of average density, thus breaking that longstanding speed barrier.
What this means in practice
- •For network designers: Optimize network structures by quickly selecting edge pairs to form cycle-free subgraphs, improving speed over older methods for medium-density networks.
- •For circuit layout engineers: Accelerate the process of designing circuit layouts by efficiently finding maximal pairs of connections without creating loops, enabling faster iterations.
A theory result. No direct application yet.
Authors
Tatsuya Terao
Abstract
In the graphic matroid parity problem, we are given an undirected multigraph $G=(V,E)$ with $n$ vertices, together with a partition of $E$ into $m$ pairs of distinct edges, and the goal is to find a maximum-cardinality collection of pairs whose union is a forest. This problem generalizes both graph matching and graphic matroid intersection. Graph matching admits the celebrated $\tilde{O}(\sqrt{n}m)$-time algorithm of Micali--Vazirani~[FOCS'80], and graphic matroid intersection admits $o(nm)$-time algorithms due to Gabow--Stallmann~[ICALP'85] and Gabow--Xu~[FOCS'89]. In contrast, for graphic matroid parity, Gabow--Stallmann~[FOCS'84 \& Combinatorica'86] gave an $O(n^2 m)$-time algorithm, and its $\tilde{O}(nm)$-time implementation by Gabow--Stallmann~[ICALP'85] had long remained the best known bound, except in very dense regimes where $m=ω(n^3)$, in which case the algebraic $\tilde{O}(n^4)$-time algorithm of Cheung--Lau--Leung~[SODA'11 \& TALG'14] is faster. We present a randomized $\tilde{O}(n^{3/2} \sqrt{m} + \sqrt{n} m)$-time algorithm for graphic matroid parity. This is the first algorithm to break the $O(nm)$-time complexity barrier for this problem outside the very dense regime. Moreover, it improves over the previous bounds except in very sparse regimes where $m=\tilde{O}(n)$ and in very dense regimes where $m = \tildeΩ(n^{3.5})$. In particular, when $m=Θ(n^2)$, our algorithm runs in $\tilde{O}(n^{2.5})$ time, which nearly matches the $\tilde{O}(n^{2.5})$-time bounds of Micali--Vazirani for graph matching and of Gabow--Xu for graphic matroid intersection in this regime.