Metraipolis › archive › dc_a78e677f8da4
Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications — arXiv:2609.01283
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.01283
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T07:19:16.210Z
- SHA-256 of the archived text
c411a091f25f4b10c5123daf8d7c2857d16cf0984bc3a3d79a09e2f345264c7e- Stable URL of this page
https://metraipolis.com/documento/dc_a78e677f8da4
How to cite
Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications — arXiv:2609.01283 — arXiv (en), https://arxiv.org/abs/2609.01283 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a78e677f8da4 (Metraipolis archive dc_a78e677f8da4, sha256 c411a091f25f4b10c5123daf8d7c2857d16cf0984bc3a3d79a09e2f345264c7e)
BibTeX
@misc{dca78e677f8da4,
title = {Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications — arXiv:2609.01283},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.01283},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a78e677f8da4; sha256 c411a091f25f4b10c5123daf8d7c2857d16cf0984bc3a3d79a09e2f345264c7e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.01283. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$- and global min-cut apply only to undirected graphs; and for matchings, arborescence and spanning-tree packings, and arboricity, no efficient oracle is known for $f>1$. We present a unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids, yielding the first oracles supporting an arbitrary number $f$ of updates across all of these problems (all constructions randomized Monte-Carlo). Concretely, we obtain efficient oracles for exact $(s,t)$-max-flow/min-cut, resolving an open problem of Baswana, Bhanja, and Pandey (ICALP'22) with near-optimal space; for all-pairs $k$-bounded flow, generalizing the near-optimal reachability oracle of Brand and Saranurak (FOCS'19, the case $k=1$); the first oracles for any $f$ for directed $s$- and global min-cut; oracles for $k$-disjoint arborescences, $k$-disjoint spanning trees, colorful spanning trees, and arboricity; and oracles for the existence of an $\alpha$-factor, with perfect matching as the case $\alpha=1$. We further introduce the \emph{subset sensitivity model}, in which updates are confined to a susceptible edge set of size $\sigma$ fixed during preprocessing. Here we decouple updates from the matroid representation and eliminate the dependence on $k$ and the matroid density altogether: all of the above are supported with $\widetilde O(f^\omega)$ query time and $O(f\sigma^2)$ space. We also prove a matching $\Omega(\min\{\sigma^2,n^2\})$-bit lower bound when $f\ge2$, establishing optimality.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-02 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.01283 — 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-17T07:07:35.201Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).