Covering minimum spanning trees of random subgraphs

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