Fast methods find multiple largest common sets in matroids with fewer queries

Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection

Data Structures and Algorithms

Summary

Imagine you have two systems each with rules about which items can be chosen, and you want to find the largest set of items that fit both systems' rules. After finding one largest set, the authors look for another different largest set, which is usually very hard. They created new algorithms that can find or confirm another largest set faster than before by making fewer checks to the rules. Their methods also let you list all the largest sets one after the other efficiently, without building large complex structures.

What this means in practice

Authors

Makoto Watanabe

Abstract

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\ne S$, and of outputting one when it exists. Writing $n=|V|$ and $r=|S|$, we give a Las Vegas algorithm using $\tilde O(n\sqrt r)$ expected independence queries and a deterministic algorithm using $\tilde O(nr^{2/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.