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,\dots ,k$. In 1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that uses $O(n{p}^{3\mathrm{/}2}+kn)$ independence oracle queries, which was the previously known best algorithm. This query complexity is $O(n^{5\mathrm{/}2})$ when $k\le n$. Our main result is to present a matroid partition algorithm that uses $\tilde{O}(k^{\mathrm{\prime }1\mathrm{/}3}np+kn)$ independence oracle queries, where $k^{\mathrm{\prime }}=\min \{k,p\}$. This query complexity is $\tilde{O}(n^{7\mathrm{/}3})$ when $k\le n$, and this improves upon the one of previous Cunningham’s algorithm. To obtain this, we present a new approach \emph{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 $\tilde{O}((n+k)\sqrt{p})$ rank oracle queries.