Faster Matroid Partition Algorithms

In the matroid partitioning problem, we are given k matroids M1 = (V, I1), dots , Mk = (V, Ik) defined over a common ground set V of n elements, and we need to find a partitionable set S subseteq V of largest possible cardinality, denoted by p. Here, a set S subseteq V is called partitionable if there exists a partition (S1, dots , Sk) of S with Si ∈ Ii for i = 1, ldots, k. In 1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that uses O(n p3/2 + k n) independence oracle queries, which was the previously known best algorithm. This query complexity is O(n5/2) when k ≤ n. Our main result is to present a matroid partition algorithm that uses tildeO(k'1/3 n p + k n) independence oracle queries, where k' = mink, p. This query complexity is tildeO(n7/3) when k ≤ n, and this improves upon the one of previous Cunningham's algorithm. To obtain this, we present a new approach edge recycling augmentation, which can be attained through new ideas: an efficient utilization of the binary search technique by Nguyen [2019] and Chakrabarty-Lee-Sidford-Singla-Wong [FOCS 2019] and a careful analysis of the independence oracle query complexity. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter k. We also present a matroid partition algorithm that uses tildeO((n + k) √p) rank oracle queries.