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 pseudoinverse, 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 almostlinear 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.01approximations 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 nontrivial 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 NonExpander Graphs}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {29:129:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18682},
URN = {urn:nbn:de:0030drops186823},
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 