A Fast Algorithm for Source-Wise Round-Trip Spanners

Abstract In this paper, we study the problem of fast constructions of source-wise round-trip spanners in weighted directed graphs. For a source vertex set S ⊆ V in a graph G ( V , E ) , an S-sourcewise round-trip spanner of G of stretch k is a subgraph H of G such that for every pair of vertices u , v ∈ S × V , their round-trip distance in H is at most k times of their round-trip distance in G. We show that for a graph G ( V , E ) with n vertices and m edges, an s-sized source vertex set S ⊆ V and an integer k > 1 , there exists an algorithm that in time O ( m s 1 / k log 5 ⁡ n ) constructs an S-sourcewise round-trip spanner of stretch O ( k log ⁡ n ) and O ( n s 1 / k log 2 ⁡ n ) edges with high probability. Compared to the fast algorithms for constructing all-pairs round-trip spanners [26] , [12] , our algorithm improves the running time and the number of edges in the spanner when k is super-constant. Compared with the existing algorithm for constructing source-wise round-trip spanners [36] , our algorithm significantly improves their construction time Ω ( min ⁡ { m s , n ω } ) (where ω ∈ [ 2 , 2.373 ) and 2.373 is the matrix multiplication exponent) to nearly linear O ( m s 1 / k log 5 ⁡ n ) , at the expense of paying an extra O ( log ⁡ n ) in the stretch. As an important building block of the algorithm, we develop a graph partitioning algorithm to partition G into clusters of bounded radius and prove that for every u , v ∈ S × V at small round-trip distance, the probability of separating them in different clusters is small. The algorithm takes the size of S as input and does not need the knowledge of S. With the algorithm and a reachability vertex size estimation algorithm, we show that the recursive algorithm for constructing standard round-trip spanners [26] can be adapted to the source-wise setting. We rigorously prove the correctness and computational complexity of the adapted algorithms. Finally, we show how to remove the dependence on the edge weight in the source-wise case.