LIPIcs.APPROX-RANDOM.2015.738.pdf
- Filesize: 0.52 MB
- 18 pages
Document
Towards Resistance Sparsifiers
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-08-13
File
Document Identifiers
Cite As Get BibTex
Michael Dinitz, Robert Krauthgamer, and Tal Wagner. Towards Resistance Sparsifiers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 738-755, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.738
Abstract
We study resistance sparsification of graphs, in which the goal is to find a sparse subgraph (with reweighted edges) that approximately preserves the effective resistances between every pair of nodes. We show that every dense regular expander admits a (1+epsilon)-resistance sparsifier of size ~O(n/epsilon), and conjecture this bound holds for all graphs on n nodes. In comparison, spectral sparsification is a strictly stronger notion and requires Omega(n/epsilon^2) edges even on the complete graph. Our approach leads to the following structural question on graphs: Does every dense regular expander contain a sparse regular expander as a subgraph? Our main technical contribution, which may of independent interest, is a positive answer to this question in a certain setting of parameters. Combining this with a recent result of von Luxburg, Radl, and Hein (JMLR, 2014) leads to the aforementioned resistance sparsifiers.
Subject Classification
Keywords
- edge sparsification
- spectral sparsifier
- graph expansion
- effective resistance
- commute time
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alexandr Andoni, Robert Krauthgamer, and David P. Woodruff. The sketching complexity of graph cuts. CoRR, abs/1403.7058, 2014. URL: http://arxiv.org/abs/1403.7058.
- Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM J. Comput., 41(6):1704-1721, 2012. URL: http://dx.doi.org/10.1137/090772873.
- A. A. Benczúr and D. R. Karger. Approximating s-t minimum cuts in Õ(n^2) time. In 28th Annual ACM Symposium on Theory of Computing, pages 47-55. ACM, 1996. URL: http://dx.doi.org/10.1145/237814.237827.
- Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, and Andrew Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures. ArXiv e-prints, abs/1401.4159, 2014. URL: http://arxiv.org/abs/1401.4159.
-
M. M. Deza and M. Laurent. Geometry of cuts and metrics. Springer-Verlag, Berlin, 1997.
- Michael Kapralov and Rina Panigrahy. Spectral sparsification via random spanners. In 3rd Innovations in Theoretical Computer Science Conference, pages 393-398. ACM, 2012. URL: http://dx.doi.org/10.1145/2090236.2090267.
- Rohit Khandekar, Subhash A. Khot, Lorenzo Orecchia, and Nisheeth K. Vishnoi. On a cut-matching game for the sparsest cut problem. Technical Report UCB/EECS-2007-177, EECS Department, University of California, Berkeley, 2007. URL: http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-177.html.
- Rohit Khandekar, Satish Rao, and Umesh V. Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4), 2009. URL: http://dx.doi.org/10.1145/1538902.1538903.
- Daniela Kühn and Deryk Osthus. Decompositions of complete uniform hypergraphs into hamilton berge cycles. J. Comb. Theory, Ser. A, 126:128-135, 2014. URL: http://dx.doi.org/10.1016/j.jcta.2014.04.010.
-
L. Lovász. Random walks on graphs: a survey. In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 353-397. János Bolyai Math. Soc., Budapest, 1996.
- D. Peleg and A. A. Schäffer. Graph spanners. J. Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
-
L. Perkovic and B. Reed. Edge coloring regular graphs of high degree. In Discrete Math.,165/166, pages 567-578, 1997.
- D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In 36th Annual ACM Symposium on Theory of Computing, pages 81-90. ACM, 2004. URL: http://dx.doi.org/10.1145/1007352.1007372.
- Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913-1926, December 2011. URL: http://dx.doi.org/10.1137/080734029.
- Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1025, July 2011. URL: http://dx.doi.org/10.1137/08074489X.
- Ulrike von Luxburg, Agnes Radl, and Matthias Hein. Hitting and commute times in large random neighborhood graphs. Journal of Machine Learning Research, 15(1):1751-1798, 2014. URL: http://jmlr.org/papers/v15/vonluxburg14a.html.