Metraipolis › archive › dc_ec657d866879
Finding and Certifying Weighted Minimum Cuts with Cut Queries — arXiv:2611.03107
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03107
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:45:46.368Z
- SHA-256 of the archived text
e62057939a178c711e696cdba7a54fed3f5731b9a32d0a7e699411c79f3531d1- Stable URL of this page
https://metraipolis.com/documento/dc_ec657d866879
How to cite
Finding and Certifying Weighted Minimum Cuts with Cut Queries — arXiv:2611.03107 — arXiv (en), https://arxiv.org/abs/2611.03107 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ec657d866879 (Metraipolis archive dc_ec657d866879, sha256 e62057939a178c711e696cdba7a54fed3f5731b9a32d0a7e699411c79f3531d1)
BibTeX
@misc{dcec657d866879,
title = {Finding and Certifying Weighted Minimum Cuts with Cut Queries — arXiv:2611.03107},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03107},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ec657d866879; sha256 e62057939a178c711e696cdba7a54fed3f5731b9a32d0a7e699411c79f3531d1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03107. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the deterministic and nondeterministic cut query complexity of minimum cut in undirected graphs with arbitrary nonnegative edge weights. For the nondeterministic case, we show that every $n$-vertex graph has an $O(n\log^2(2n))$-query certificate of its exact global minimum-cut value, such that any other nonnegatively weighted graph on the same vertex set that agrees on these queries has the same minimum cut value. A key ingredient is a way to certify a maximum $s$--$t$ flow value with only $O(n)$ cut queries. For the deterministic case we give an algorithm that finds an exact global minimum cut using $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries. Previously no $O(n^{2-\varepsilon})$ deterministic bound was known for arbitrary nonnegatively weighted graphs. The algorithm follows Karger's two-respecting tree approach. The key new ingredient is a deterministic construction of a weak skeleton of the input graph $G$: an explicit weighted graph $H$ in which every minimum cut of $G$ is a $5/4$-approximate minimum cut.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.03107 — 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-11-03T11:07:52.255Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).