DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.124

An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases

Authors: Sanjeev Khanna, Aaron Putterman, and Junkai Song

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We study the parallel (adaptive) complexity of the classic problem of finding a basis in an n-element matroid, given access via an independence oracle. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988; hereafter KUW) initiated this study, showing that O(√n) adaptive rounds suffice for any matroid, and that Ω̃(n^{1/3}) rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS 2025; hereafter KPS) achieved Õ(n^{7/15}) rounds, the first improvement since KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in Õ(n^{3/7}) rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously. Specifically, our framework introduces three new ideas: 1) A new subset-based decomposition that provides precise guarantees on how random circuits intersect groups of elements, yet remains computable in few adaptive rounds. 2) A new method for identifying and removing redundant elements in bulk, based on short circuit witnesses that certify redundancy across large portions of the matroid. 3) An adaptive early-stopping strategy that uses the evolving structure of the matroid to decide when to contract or delete, preventing wasted rounds. Each of these contributions, in isolation, already yields meaningful improvements over the round complexity achieved in KPS; their combination enables our main result of Õ(n^{3/7}) rounds. As further consequences, incorporating our improved basis-finding algorithm into known reductions yields an Õ(n^{17/21})-round parallel algorithm for matroid intersection, as well as an Õ(n^{3/7})-round parallel algorithm for approximate monotone submodular maximization under a matroid constraint.

Cite as

Sanjeev Khanna, Aaron Putterman, and Junkai Song. An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 124:1-124:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2026.124,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Song, Junkai},
  title =	{{An Õ(n^\{3/7\}) Round Parallel Algorithm for Matroid Bases}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{124:1--124:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.124},
  URN =		{urn:nbn:de:0030-drops-265130},
  doi =		{10.4230/LIPIcs.ICALP.2026.124},
  annote =	{Keywords: parallel algorithms, matroids}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.125

Optimal Parallel Basis Finding in Graphic and Related Matroids

Authors: Sanjeev Khanna, Aaron Putterman, and Junkai Song

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We study the parallel complexity of finding a basis of a graphic matroid under independence-oracle access. Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988) initiated the study of this problem and established two algorithms for finding a spanning forest: one running in O(log m) rounds with m^{Θ(log m)} queries, and another, for any d ∈ ℤ^+, running in O(m^{2/d}) rounds with Θ(m^d) queries. A key open question they posed was whether one could simultaneously achieve polylogarithmic rounds and polynomially many queries. We give a deterministic algorithm that uses O(log m) adaptive rounds and poly(m) non-adaptive queries per round to return a spanning forest on m edges, and complement this result with a matching Ω(log m) lower bound for any (even randomized) algorithm with poly(m) queries per round. Thus, the adaptive round complexity for graphic matroids is characterized exactly, settling this long-standing problem. Beyond graphs, we show that our framework also yields an O(log m)-round, poly(m)-query algorithm for any binary matroid satisfying a smooth circuit counting property, implying, among others, an optimal O(log m)-round parallel algorithms for finding bases of cographic matroids. Finally, we conjecture a natural strengthening of known circuit-counting bounds for the much broader class of regular matroids and even an extension to so-called max-flow min-cut matroids; assuming it, our algorithm achieves the same O(log m) rounds and poly(m) queries for all such matroids - which includes graphic and cographic matroids as special cases.

Cite as

Sanjeev Khanna, Aaron Putterman, and Junkai Song. Optimal Parallel Basis Finding in Graphic and Related Matroids. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 125:1-125:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2026.125,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Song, Junkai},
  title =	{{Optimal Parallel Basis Finding in Graphic and Related Matroids}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{125:1--125:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.125},
  URN =		{urn:nbn:de:0030-drops-265143},
  doi =		{10.4230/LIPIcs.ICALP.2026.125},
  annote =	{Keywords: parallel algorithms, matroids}
}

Search Results

Documents authored by Song, Junkai

An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases

Abstract

Cite as

Optimal Parallel Basis Finding in Graphic and Related Matroids

Abstract

Cite as

Thanks for your feedback!

Could not send message