Optimal Electrical Oblivious Routing on Expanders

Abstract

In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an $m$-edge graph $G=(V,E)$ that is a $\hat{I}¦$-expander, i.e. where $|\partial S|\ge \hat{I}¦\cdot \mathrm{vol}(S)$ for every $S\subseteq V,\mathrm{vol}(S)\le \mathrm{vol}(V)/2$. Beyond its simplicity and structural importance, this question is well-motivated by the current state-of-the-art of fast algorithms for ${\ell }_{\infty }$ oblivious routings that reduce to the expander-case which is in turn solved by electrical flow routing. Our main result proves that the electrical routing is an $O(\hat{I}{¦}^{-1}\log m)$-competitive oblivious routing in the ${\ell }_1$- and ${\ell }_{\infty }$-norms. We further observe that the oblivious routing is $O({\log }^{2}m)$-competitive in the ${\ell }_2$-norm and, in fact, $O(\log m)$-competitive if ${\ell }_2$-localization is $O(\log m)$ which is widely believed. Using these three upper bounds, we can smoothly interpolate to obtain upper bounds for every $p\in [2,\infty ]$ and $q$ given by $1/p+1/q=1$. Assuming ${\ell }_2$-localization in $O(\log m)$, we obtain that in ${\ell }_p$ and ${\ell }_q$, the electrical oblivious routing is $O(\hat{I}{¦}^{-(1-2/p)}\log m)$ competitive. Using the currently known result for ${\ell }_2$-localization, this ratio deteriorates by at most a sublogarithmic factor for every $p,q\ne 2$. We complement our upper bounds with lower bounds that show that the electrical routing for any such $p$ and $q$ is $\hat{I}\text{c◯}(\hat{I}{¦}^{-(1-2/p)}\log m)$-competitive. This renders our results in ${\ell }_1$ and ${\ell }_{\infty }$ unconditionally tight up to constants, and the result in any ${\ell }_p$- and ${\ell }_q$-norm to be tight in case of ${\ell }_2$-localization in $O(\log m)$.

To appear in ICALP 2024