Metraipolis › archive › dc_f8e291e352ea

Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection — arXiv:2609.18199

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.18199
License (as archived): CC0-1.0
Archived: 2026-10-15T17:09:18.571Z
SHA-256 of the archived text: 84e9cad721344bed1dcaf10554cc7e055e379b3b6ccbb1b22635aa2303a9d2ec
Stable URL of this page: https://metraipolis.com/documento/dc_f8e291e352ea

How to cite

Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection — arXiv:2609.18199 — arXiv (en), https://arxiv.org/abs/2609.18199 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f8e291e352ea (Metraipolis archive dc_f8e291e352ea, sha256 84e9cad721344bed1dcaf10554cc7e055e379b3b6ccbb1b22635aa2303a9d2ec)

BibTeX

@misc{dcf8e291e352ea,
  title = {Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection — arXiv:2609.18199},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18199},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f8e291e352ea; sha256 84e9cad721344bed1dcaf10554cc7e055e379b3b6ccbb1b22635aa2303a9d2ec},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18199. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.18199 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.260Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).