2023/02/20 by Blikstad, Joakim, Mukhopadhyay, Sagnik, Nanongkai, Danupon +1 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2302.09796
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 Ok(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 Ok(n√(r)) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An Ok(|E|+|V|√(|V|))-time algorithm for the k-disjoint spanning tree problem. This improves the Ok(|V|√(|E|)) bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. * We show a matroid intersection algorithm with O(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 (Ω(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].