Premium
Covering minimum spanning trees of random subgraphs
Author(s) -
Goemans Michel X.,
Vondrák Jan
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20115
Subject(s) - combinatorics , mathematics , spanning tree , random graph , vertex (graph theory) , minimum spanning tree , minimum degree spanning tree , discrete mathematics , upper and lower bounds , matroid , shortest path tree , graph , mathematical analysis
We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p , and subgraphs generated as a random subset of edges, each edge with probability p . Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n , and let b = 1/(1 − p ). We show that in both random models, for any weighted graph G , there is a set of edges Q of cardinality O ( n log b n ) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O ( kn ) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O ( n log b n ) on the size of a covering set in a matroid of rank n , which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006