2026-07-22T03:24:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16366 2024-03-06T10:57:17Z ddc:004 open_access

Sublinear-Round Parallel Matroid Intersection Blikstad, Joakim Matroid Intersection Combinatorial Optimization Parallel Algorithms Despite a lot of recent progress in obtaining faster sequential matroid intersection algorithms, the fastest parallel poly(n)-query algorithm was still the straightforward O(n)-round parallel implementation of Edmonds' augmenting paths algorithm from the 1960s. Very recently, Chakrabarty-Chen-Khanna [FOCS'21] showed the lower bound that any, possibly randomized, parallel matroid intersection algorithm making poly(n) rank-queries requires Ω̃(n^{1/3}) rounds of adaptivity. They ask, as an open question, if the lower bound can be improved to Ω̃(n), or if there can be sublinear-round, poly(n)-query algorithms for matroid intersection. We resolve this open problem by presenting the first sublinear-round parallel matroid intersection algorithms. Perhaps surprisingly, we do not only break the Õ(n)-barrier in the rank-oracle model, but also in the weaker independence-oracle model. Our rank-query algorithm guarantees O(n^{3/4}) rounds of adaptivity, while the independence-query algorithm uses O(n^{7/8}) rounds of adaptivity, both making a total of poly(n) queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joakim Blikstad 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.25 urn:nbn:de:0030-drops-163662 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.25 eng https://creativecommons.org/licenses/by/4.0/legalcode