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
- •For combinatorial optimization engineers: Decide and find different maximum solutions in problems modeled by matroids using fewer independence queries to improve efficiency.
- •For algorithm developers for network design: Enumerate all optimal common independent sets in matroid intersection problems more quickly without constructing large exchange graphs.
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.