2026-07-26T19:18:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5333 2024-03-06T10:36:20Z ddc:004 open_access

Towards Resistance Sparsifiers Dinitz, Michael Krauthgamer, Robert Wagner, Tal edge sparsification spectral sparsifier graph expansion effective resistance commute time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Dinitz and Robert Krauthgamer and Tal Wagner 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.738 urn:nbn:de:0030-drops-53334 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.738 eng https://creativecommons.org/licenses/by/3.0/legalcode