{"ID":2845537,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.04826","arxiv_id":"2511.04826","title":"Optimal Parallel Basis Finding in Graphic and Related Matroids","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 \\in \\mathbb{Z}^+$, 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 $\\mathrm{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 $\\mathrm{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, $\\mathrm{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.","short_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, a...","url_abs":"https://arxiv.org/abs/2511.04826","url_pdf":"https://arxiv.org/pdf/2511.04826v1","authors":"[\"Sanjeev Khanna\",\"Aaron Putterman\",\"Junkai Song\"]","published":"2025-11-06T21:27:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}