Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.738
URN: urn:nbn:de:0030-drops-53334
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5333/
Dinitz, Michael ; Krauthgamer, Robert ; Wagner, Tal
Towards Resistance Sparsifiers
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{dinitz_et_al:LIPIcs:2015:5333,
author = {Michael Dinitz and Robert Krauthgamer and Tal Wagner},
title = {{Towards Resistance Sparsifiers}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {738--755},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-89-7},
ISSN = {1868-8969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5333},
URN = {urn:nbn:de:0030-drops-53334},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.738},
annote = {Keywords: edge sparsification, spectral sparsifier, graph expansion, effective resistance, commute time}
}
| Keywords: | edge sparsification, spectral sparsifier, graph expansion, effective resistance, commute time | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 13.08.2015 |
