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.

翻译：我们研究了在图拟阵的独立性预言机访问下寻找基的并行复杂度。Karp、Upfal和Wigderson（FOCS 1985，JCSS 1988）开创了对该问题的研究，并提出了两种寻找生成森林的算法：一种在$O(\\log m)$轮内运行，使用$m^{\\Theta(\\log m)}$次查询；另一种针对任意$d \\in \\mathbb{Z}^+$，在$O(m^{2/d})$轮内运行，使用$\\Theta(m^d)$次查询。他们提出的一个关键开放问题是能否同时实现多对数轮数和多项式次数的查询。我们给出了一种确定性算法，该算法使用$O(\\log m)$轮自适应轮数，每轮进行$\\mathrm{poly}(m)$次非自适应查询，以返回在$m$条边上的生成森林，并通过一个匹配的$\\Omega(\\log m)$下界来补充这一结果，该下界适用于任何每轮进行$\\mathrm{poly}(m)$次查询的（即使是随机化）算法。因此，图拟阵的自适应轮复杂度被精确刻画，解决了这一长期存在的问题。在图之外，我们展示了我们的框架还为任何满足平滑回路计数性质的二元拟阵提供了一个$O(\\log m)$轮、$\\mathrm{poly}(m)$次查询的算法，这尤其意味着为寻找余图拟阵的基提供了最优的$O(\\log m)$轮并行算法。