Fast Algorithms via Dynamic-Oracle Matroids

Abstract

We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" algorithm whose performance matches previous results developed in various papers. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. * We show an algorithm with ${\tilde{O}}_k(n+r\sqrt{r})$ dynamic-rank-query and time complexities for the matroid union problem over $k$ matroids. This implies the following consequences. (i) An improvement over the ${\tilde{O}}_k(n\sqrt{r})$ bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An ${\tilde{O}}_k(|E|+|V|\sqrt{|V|})$-time algorithm for the $k$-disjoint spanning tree problem. This improves the ${\tilde{O}}_k(|V|\sqrt{|E|})$ bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. * We show a matroid intersection algorithm with $\tilde{O}(n\sqrt{r})$ dynamic-rank-query and time complexities. This implies new bounds for some problems and bounds that match the classic ones obtained in various papers, e.g. colorful spanning tree [Gabow-Stallmann ICALP'85], graphic matroid intersection [Gabow-Xu FOCS'89], simple scheduling matroid intersection [Xu-Gabow ISAAC'94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a "unified" algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously. * We show simple super-linear ($\Omega (n\log n)$) query lower bounds for matroid intersection in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous ${\log }_2(3)n-o(n)$ bound by Harvey [SODA'08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS'19].

To appear at STOC 2023. Abstract shortened to meet arXiv requirement