arXiv preprint ·
Stochastic Minimum Spanning Tree Identification with Binary Weights
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.