Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection

Let ${\mathcal{M}}_1,{\mathcal{M}}_2$ be two matroids on a common ground set $V$, given by independence oracles, and let $S$ be a maximum-cardinality common independent set. We study the problem of deciding whether there exists another maximum common independent set $T\mathrm{\ne }S$, and of outputting one when it exists. Writing $n=\mathrm{\mid }V\mathrm{\mid }$ and $r=\mathrm{\mid }S\mathrm{\mid }$, we give a Las Vegas algorithm using $\tilde{O}(n\sqrt{r})$ expected independence queries and a deterministic algorithm using $\tilde{O}(n{r}^{2\mathrm{/}3})$ queries. As an application, all maximum common independent sets can be enumerated with at most two another-solution calls between consecutive outputs and after the last output; if there are $L$ solutions, exactly $2L-1$ such calls are made. Neither algorithm constructs the exchange graph. Instead, they perform Kahn-style source peeling through two deletion-only data structures. One side uses the heavy/light categorization of Blikstad, van den Brand, Mukhopadhyay, and Nanongkai. For the opposite side, where no transposed oracle is available, we give a collective randomized classifier and a deterministic capacity-saturation certificate.