Faster Matroid Partition Algorithms

In the matroid partitioning problem, we are given \(k\) matroids \(\mathcal{M}_{1}=(V,\mathcal{I}_{1}),\dots,\mathcal{M}_{k}=(V,\mathcal{I}_{k})\) 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 \((S_{1},\dots,S_{k})\) of \(S\) with \(S_{i}\in\mathcal{I}_{i}\) for \(i=1,\ldots,k\) . In 1986, Cunningham presented a matroid partition algorithm that uses \(O(np^{3/2}+kn)\) independence oracle queries, which was the previously known best algorithm. This query complexity is \(O(n^{5/2})\) when \(k\leq n\) . Our main result is to present a matroid partition algorithm that uses \(\tilde{O}(k^{\prime 1/3}np + kn)\) independence oracle queries, where \(k^{\prime}=\min\{k,p\}\) . This query complexity is \(\tilde{O}(n^{7/3})\) when \(k\leq n\) , which improves upon that of Cunningham’s algorithm. To obtain our algorithm, we present a new approach edge recycling augmentation , which can be attained through new ideas: an efficient utilization of the binary search technique by Nguy \(\tilde{{\hat{\text{e}}}}\) n and Chakrabarty et al. 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 \(\tilde{O}((n+k)\sqrt{p})\) rank oracle queries.