Metraipolis › archive › dc_76feb357565a
Stochastic Minimum Spanning Tree Identification with Binary Weights — arXiv:2610.40844
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.40844
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-02T08:06:42.702Z
- SHA-256 of the archived text
fb879c9556cb20bc02bb0d41f30414d6ab59a207bb37aef244b029f3c2977595- Stable URL of this page
https://metraipolis.com/documento/dc_76feb357565a
How to cite
Stochastic Minimum Spanning Tree Identification with Binary Weights — arXiv:2610.40844 — arXiv (en), https://arxiv.org/abs/2610.40844 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_76feb357565a (Metraipolis archive dc_76feb357565a, sha256 fb879c9556cb20bc02bb0d41f30414d6ab59a207bb37aef244b029f3c2977595)
BibTeX
@misc{dc76feb357565a,
title = {Stochastic Minimum Spanning Tree Identification with Binary Weights — arXiv:2610.40844},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.40844},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_76feb357565a; sha256 fb879c9556cb20bc02bb0d41f30414d6ab59a207bb37aef244b029f3c2977595},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40844. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce the Stochastic MST Identification Problem, with binary weights. In this problem, we need to identify a minimum spanning tree (MST) of a graph, each of whose edge weights is either 0 or 1. The weight of each edge $e$ is a random variable which is 1 with probability $p_e$ and 0 with probability $1-p_e$. The probability $p_e$ is given for each edge $e$, but the realized weight of an edge can only be determined by querying the edge. The problem is then to determine a strategy for querying the edges of the graph that minimizes the expected number of queries that need to be performed until we can identify a subset of edges that form an MST of the graph. We address both adaptive and non-adaptive versions of this problem. For the non-adaptive version of our Stochastic MST Identification problem, we give an $O(\log E)$-approximation algorithm via a reduction to submodular ranking. For the adaptive version, we show that solving the problem is trivial when all $p_e$ are equal to 1/2, because of a relation to the Tutte polynomial. However, computing the expected cost of an optimal querying strategy is #P-hard, even when all $p_e$ equal $\frac{1}{2}$. For arbitrary $p_e$ values, we present a constant-factor approximation algorithm for simple planar graphs. We investigate the question of whether the submodular goal value approach of Deshpande et al. could be used to achieve a $\log$-factor approximation algorithm that would work for arbitrary $p_e$ values and general graphs. In this context, we address the structural question of determining optimal submodular goal values for MST identification in graphs.
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/2610.40844 — 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-02T07:45:15.765Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).