Improved Online Reachability Preservers

Abstract

A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an $n$-node directed input graph $G$ among a set of given demand pairs $P$ of size $|P|=p$. We give constructions of sparse reachability preservers in the online setting, where $G$ is given on input, the demand pairs $(s,t)\in P$ arrive one at a time, and we must irrevocably add edges to a preserver $H$ to ensure reachability for the pair $(s,t)$ before we can see the next demand pair. Our main results are: -- There is a construction that guarantees a maximum preserver size of $$|E(H)|\le O\left(n^{0.72}{p}^{0.56}+n^{0.6}{p}^{0.7}+n\right).$$ This improves polynomially on the previous online upper bound of $O(\min \{n{p}^{0.5},n^{0.5}p\})+n$, implicit in the work of Coppersmith and Elkin [SODA '05]. -- Given a promise that the demand pairs will satisfy $P\subseteq S\times V$ for some vertex set $S$ of size $|S|=:\ddot{I}ƒ$, there is a construction that guarantees a maximum preserver size of $$|E(H)|\le O\left((np\ddot{I}ƒ{)}^{1/2}+n\right).$$ A slightly different construction gives the same result for the setting $P\subseteq V\times S$. This improves polynomially on the previous online upper bound of $O(\ddot{I}ƒn)$ (folklore). All of these constructions are polynomial time, deterministic, and they do not require knowledge of the values of $p,\ddot{I}ƒ$, or $S$. Our techniques also give a small polynomial improvement in the current upper bounds for offline reachability preservers, and they extend to a stronger model in which we must commit to a path for all possible reachable pairs in $G$ before any demand pairs have been received. As an application, we improve the competitive ratio for Online Unweighted Directed Steiner Forest to $O(n^{3/5+\epsilon })$.

SODA 2025