Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
Keerti Choudhary, Omer Gold · Society for Industrial and Applied Mathematics eBooks · 2019
Given a directed graph G = (V, E) on n vertices and m edges, a subgraph H = (V, Eʹ ⊆ E) is defined to be a t-diameter 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 ≪ n2 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 Õ(m)-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 time algorithm for this problem, and showed that there is no O(n2−o(1)) 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 (2+ε)-approximation and O(n1+o(1)) amortized update time.