Improved Online Reachability Preservers
Greg Bodwin, Tuong Le · Society for Industrial and Applied Mathematics eBooks · 2025
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 ) ∈ 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: