Twice-ramanujan sparsifiers

ABSTRACT

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every d > 1 and every undirected, weighted graph G = (V,E,w) on n vertices, there exists a weighted graph H=(V,F,~{w}) with at most ⌈d(n-1)⌉ edges such that for every x ∈ R^V, [x^T L_G x ≤ x^T L_H x ≤ ((d+1+2√d)/(d+1-2√d)) • x^T L_G x] where L_G and L_H are the Laplacian matrices of G and H, respectively. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing H.

REFERENCES

• 1: C. A. Akemann and J. Anderson. Lyapunov theorems for operator algebras. Mem. Amer. Math. Soc., 94, 1991.
• 2: N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
• 3: 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]
• 4: J. Bourgain and L. Tzafriri. On a problem of Kadison and Singer. J. Reine Angew. Math., 420:1--43, 1991.
• 5: Peter G. Casazza and Janet C. Tremain. The Kadison-Singer problem in mathematics and engineering. Proceedings of the National Academy of Sciences of the United States of America, 103(7):2032--2039, 2006.
• 6: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• 7: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 8: Navin Goyal , Luis Rademacher , Santosh Vempala, Expanders via random spanning trees, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.576-585, January 04-06, 2009, New York, New York
• 9: Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439--561, 2006.
• 10: Rohit Khandekar , Satish Rao , Umesh Vazirani, Graph partitioning using single commodity flows, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132574]
• 11: A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 12: G. A. Margulis. Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problems of Information Transmission, 24(1):39--46, July 1988.
• 13: A. Nilli, On the second eigenvalue of a graph, Discrete Mathematics, v.91 n.2, p.207-210, Aug. 28, 1991 [doi>10.1016/0012-365X(91)90112-F]
• 14: Mark Rudelson. Random vectors in the isotropic position. J. of Functional Analysis, 163(1):60--72, 1999.
• 15: 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]
• 16: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 17: Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs/cs/0607105, 2008. Available at http://www.arxiv.org/abs/cs.NA/0607105.
• 18: Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. CoRR, abs/0808.4134, 2008. Available at http://arxiv.org/abs/0808.4134.
• 19: Nik Weaver. The Kadison-Singer problem in discrepancy theory. Discrete Mathematics, 278(1-3):227 -- 239, 2004.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
expander graphs, spectral graph theory