DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.738

Towards Resistance Sparsifiers

Authors: Michael Dinitz, Robert Krauthgamer, and Tal Wagner

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.APPROX-RANDOM.2015.738,
  author =	{Dinitz, Michael and Krauthgamer, Robert and Wagner, Tal},
  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 =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.738},
  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}
}

Search Results

Documents authored by Wagner, Tal

Towards Resistance Sparsifiers

Abstract

Cite as

Thanks for your feedback!

Could not send message