Expanders via random spanning trees

ABSTRACT

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 = Ω(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is 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. Splicers also turn out to have applications to graph cut-sparsification where the goal is to approximate every cut using only a small subgraph of the original graph. For random graphs, splicers provide simple algorithms for sparsifiers of size O(n) that approximate every cut to within a factor of O(log n).

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007916]
• 2: David J. Aldous, The random walk construction of uniform spanning trees and uniform labelled trees, SIAM Journal on Discrete Mathematics, v.3 n.4, p.450-465, November 1990 [doi>10.1137/0403039]
• 3: Noga Alon , Michael Capalbo, Finding Disjoint Paths in Expanders Deterministically and Online, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.518-524, October 21-23, 2007 [doi>10.1109/FOCS.2007.28]
• 4: N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience {John Wiley & Sons}, New York, second edition, 2000.
• 5: J. Batson, D. A. Spielman, and N. Srivastava. Twiceramanujan sparsifiers. arXiv:0808.0163v1, 2008.
• 6: András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
• 7: A. Broder, Generating random spanning trees, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.442-447, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63516]
• 8: Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M]
• 9: Tomás Feder , Milena Mihail, Balanced matroids, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.26-38, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129716]
• 10: O. Goldreich. Randomized Methods in Computation, Lecture 2. Lecture Notes, available at: http://www.wisdom.weizmann.ac.il/~oded/rnd.html, 2001.
• 11: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
• 12: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 13: L. Lovász. Random walks on graphs: A survey. In Combinatorics, Paul Erdős is Eighty, Vol. 2 (ed. D. Miklós, V. T. Sós, T. Szőnyi), János Bolyai Mathematical Society, Budapest, pages 353--398, 1996.
• 14: R. Lyons and Y. Peres. Probability on Trees and Networks. Book in progress, available at: http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html, 2005.
• 15: Milena Mihail , Christos Papadimitriou , Amin Saberi, On certain connectivity properties of the internet topology, Journal of Computer and System Sciences, v.72 n.2, p.239-251, March 2006 [doi>10.1016/j.jcss.2005.06.009]
• 16: Murtaza Motiwala , Megan Elmore , Nick Feamster , Santosh Vempala, Path splicing, ACM SIGCOMM Computer Communication Review, v.38 n.4, October 2008
• 17: Murtaza Motiwala , Megan Elmore , Nick Feamster , Santosh Vempala, Path splicing, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 18: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 19: R. Pemantle. Toward a theory of negative dependence. J. Math. Phys., 41:1371--1390, 2000.
• 20: James Gary Propp , David Bruce Wilson, How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph, Journal of Algorithms, v.27 n.2, p.170-217, May 1, 1998 [doi>10.1006/jagm.1997.0917]
• 21: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 22: S. Shenker. We dream of geni: Exploring radical network designs. Plenary talk at FCRC, 2007. http://lazowska.cs.washington.edu/fcrc/Shenker.FCRC.pdf.
• 23: Daniel A. Spielman , Nikhil Srivastava, Graph sparsification by effective resistances, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374456]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms