Fast Algorithms via Dynamic-Oracle Matroids

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 tildeOk(n+r√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 tildeOk(n√r) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An tildeOk(|E|+|V|√|V|)-time algorithm for the k-disjoint spanning tree problem. This improves the tildeOk(|V|√|E|) bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. * We show a matroid intersection algorithm with tildeO(n√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(nlog n)) query lower bounds for matroid intersection in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log2(3)n - o(n) bound by Harvey [SODA'08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS'19].