TY - JOUR
T1 - A fast algorithm for source-wise round-trip spanners
AU - Zhu, Chun Jiang
AU - Han, Song
AU - Lam, Kam-Yiu
PY - 2021/7/12
Y1 - 2021/7/12
N2 - 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 (ms1/k log5 n) constructs an S-sourcewise round-trip spanner of stretch O (k log n) and O (ns1/k log2 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{ms, nω}) (where ω ∈ [2, 2.373) and 2.373 is the matrix multiplication exponent) to nearly linear O (ms1/k log5 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.
AB - 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 (ms1/k log5 n) constructs an S-sourcewise round-trip spanner of stretch O (k log n) and O (ns1/k log2 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{ms, nω}) (where ω ∈ [2, 2.373) and 2.373 is the matrix multiplication exponent) to nearly linear O (ms1/k log5 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.
KW - Graph algorithms
KW - Graph partitioning
KW - Graph spanners
KW - Round-trip spanners
UR - http://www.scopus.com/inward/record.url?scp=85106952442&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85106952442&origin=recordpage
U2 - 10.1016/j.tcs.2021.05.019
DO - 10.1016/j.tcs.2021.05.019
M3 - 21_Publication in refereed journal
VL - 876
SP - 34
EP - 44
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -