2026-09-08T02:22:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26514 2026-09-05T19:46:12Z ddc:004 open_access

Optimal Parallel Basis Finding in Graphic and Related Matroids Khanna, Sanjeev Putterman, Aaron Song, Junkai parallel algorithms matroids 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sanjeev Khanna and Aaron Putterman and Junkai Song 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.125 urn:nbn:de:0030-drops-265143 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.125 eng https://creativecommons.org/licenses/by/4.0/legalcode