Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms

Given a directed graph G " pV, Eq on n vertices and m edges, a subgraph H " pV, E 1 Ď Eq is defined to be a tdiameter spanner if the diameter of H is at most t times the diameter of G. We show the existence of (and algorithms to compute) various t-diameter spanners with a sparse set of edges and t ă 2, for directed graphs. In addition, we show that our spanner constructions give tight bounds on the number of edges. To the best of our knowledge, our work is the first to focus on the existence of various sparse (with ! n 2 edges) diameter spanners of stretch ă 2, for directed graphs.

We also study eccentricity spanner, which is a subgraph that approximately preserves all vertex eccentricities of the original graph. As an application of our eccentricity spanner construction, we obtain the first r Opmq-time algorithm for computing 2-approximation of vertex eccentricities in general directed graphs. This improves the result of Backurs et al. [STOC 2018] who gave an r Opm ? nq time algorithm for this problem, and showed that there is no Opn 2´op1q q time algorithm that achieves approximation better than 2, unless SETH fails; this shows that our approximation factor is essentially tight.

Finally, we study extremal distance spanners under dynamic settings. For dynamic diameter spanners, we provide incremental and decremental algorithms with a subquadratic total update time. For dynamic eccentricities and eccentricity spanner, we provide incremental and decremental algorithms with p2εq-approximation and Opn 1op1q q amortized update time.