Improved Online Reachability Preservers

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:

• There is a construction that guarantees a maximum preserver size of

This improves polynomially on the previous online upper bound of O(minnp 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 ⊆ S × V for some vertex set S of size |S| =: σ, there is a construction that guarantees a maximum preserver size of

A slightly different construction gives the same result for the setting P ⊆ V × S. This improves polynomially on the previous online upper bound of O(σn) (folklore).

All of these constructions are polynomial time, deterministic, and they do not require knowledge of the values of p, σ, or S. Our techniques also give a small polynomial improvement in the current upper bounds for offline reachability preservers, and our results extend to an even 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+ε ), improving on the previous bound of O(n 2/3+ε ) [Grigorescu, Lin, Quanrud APPROX-RANDOM '21].