License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.29
URN: urn:nbn:de:0030-drops-186823
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18682/
Cai, Dongrun ;
Chen, Xue ;
Peng, Pan
Effective Resistances in Non-Expander Graphs
Abstract
Effective resistances are ubiquitous in graph algorithms and network analysis. For an undirected graph G, its effective resistance R_G(s,t) between two vertices s and t is defined as the equivalent resistance between s and t if G is thought of as an electrical network with unit resistance on each edge. If we use L_G to denote the Laplacian matrix of G and L_G^† to denote its pseudo-inverse, we have R_G(s,t) = (?_s-?_t)^⊤ L^† (?_s-?_t) such that classical Laplacian solvers [Daniel A. Spielman and Shang{-}Hua Teng, 2014] provide almost-linear time algorithms to approximate R_G(s,t).
In this work, we study sublinear time algorithms to approximate the effective resistance of an adjacent pair s and t. We consider the classical adjacency list model [Ron, 2019] for local algorithms. While recent works [Andoni et al., 2018; Peng et al., 2021; Li and Sachdeva, 2023] have provided sublinear time algorithms for expander graphs, we prove several lower bounds for general graphs of n vertices and m edges:
1) It needs Ω(n) queries to obtain 1.01-approximations of the effective resistance of an adjacent pair s and t, even for graphs of degree at most 3 except s and t.
2) For graphs of degree at most d and any parameter ?, it needs Ω(m/?) queries to obtain c ⋅ min{d,?}-approximations where c > 0 is a universal constant. Moreover, we supplement the first lower bound by providing a sublinear time (1+ε)-approximation algorithm for graphs of degree 2 except the pair s and t.
One of our technical ingredients is to bound the expansion of a graph in terms of the smallest non-trivial eigenvalue of its Laplacian matrix after removing edges. We discover a new lower bound on the eigenvalues of perturbed graphs (resp. perturbed matrices) by incorporating the effective resistance of the removed edge (resp. the leverage scores of the removed rows), which may be of independent interest.
BibTeX - Entry
@InProceedings{cai_et_al:LIPIcs.ESA.2023.29,
author = {Cai, Dongrun and Chen, Xue and Peng, Pan},
title = {{Effective Resistances in Non-Expander Graphs}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {29:1--29:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18682},
URN = {urn:nbn:de:0030-drops-186823},
doi = {10.4230/LIPIcs.ESA.2023.29},
annote = {Keywords: Sublinear Time Algorithm, Effective Resistance, Leverage Scores, Matrix Perturbation}
}
|
Keywords: |
|
Sublinear Time Algorithm, Effective Resistance, Leverage Scores, Matrix Perturbation |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
