Fully Dynamic Random-Walk Quantities on Undirected Expanders and $\kappa$-Uniform Directed Graphs

Abstract

We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has spectral gap at least $\gamma$, we give a $(1\pm \epsilon )$ effective-resistance data structure with expected update time $O({\gamma }^{-4}{\epsilon }^{-2}\log n{\log }^4(n/\epsilon ))$ and expected $O(1)$ query time. For directed graphs, somewhat surprisingly, the OMv conjecture precludes a fast data structure based on rapid mixing conditions alone. To address this, we introduce the notion of $\kappa$-uniform directed graphs, which requires the stationary distribution to $\kappa$-approximate the uniform distribution, and show that in this setting, random walk based data structures with $\text{poly}(\kappa ,\log n,{\epsilon }^{-1})$ update/query times are possible.