Expanders via Random Spanning Trees

Details Expanders via Random Spanning Trees Expanders via Random Spanning Trees

2008-07-09

arxiv.org/abs/0807.1496v1

Computer Science

Discrete Mathematics

Scientific paper

Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two random spanning trees approximates the expansion of every cut of the graph to within a factor of O(log n). For the random graph G_{n,p}, for p> c log{n}/n, two spanning trees give an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary -- each spanning tree can be produced independently using an algorithm by Aldous and Broder: a random walk in the graph with edges leading to previously unvisited vertices included in the tree. A second important application of splicers is to graph sparsification where the goal is to approximate every cut (and more generally the quadratic form of the Laplacian) using only a small subgraph of the original graph. Benczur-Karger as well as Spielman-Srivastava have shown sparsifiers with O(n log n/eps^2)$ edges that achieve approximation within factors 1+eps and 1-eps. Their methods, based on independent sampling of edges, need Omega(n log n) edges to get any approximation (else the subgraph could be disconnected) and leave open the question of linear-size sparsifiers. Splicers address this question for random graphs by providing sparsifiers of size O(n) that approximate every cut to within a factor of O(log n).

Affiliated with

Also associated with

No associations

Rating

Expanders via Random Spanning Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Expanders via Random Spanning Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expanders via Random Spanning Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-688432