论文标题
稀疏的时间跨度较低
Sparse Temporal Spanners with Low Stretch
论文作者
论文摘要
时间图是一个无向图$ g =（v，e）$，以及一个函数，该函数在$ e $中为每个边缘分配一个时间标签。 $ g $的一条路径，带有非降低时间标签的路径称为时间路径，从$ u $到$ v $的距离是临时路径的最小长度（即边缘数），从$ u $到$ v $。 $ g $的时间$α$ spanner是一个（时间）子图$ h $，它保留了$ v $中任何一对顶点之间的距离，最大乘以$α$。 $ h $的大小是其边缘的数量。 在这项工作中，我们研究了时间跨度的尺寸拉伸折衷。我们表明，时间集团总是接纳一个时间$（2K-1） - $ spanner，带有$ \ tilde {o}（kn^{1+ \ frac {1} {1} {k}}）$ edges，其中$ k> 1 $是一个选择的整数参数。选择$ k = \ lfloor \ log n \ rfloor $，我们获得了一个时间$ o（\ log n）$ - 带有$ \ tilde {o}（n）$ edges，其大小几乎相同（最多可与对数因素）作为时间范围的时间（Casteigts et al.Jcss peative in。 然后，我们考虑一般的时间图。由于任何具有连接性的时间子图[Axiotis等，iCalp'16]可能需要$ω（n^2）$边缘，因此我们专注于近似于单个源的距离。我们表明，对于任何小$ \ varepsilon> 0 $，$ \ tilde {o}（n/\ log（1+ \ varepsilon））$边缘足以获得$（1+ \ varepsilon）$。该结果本质上是紧密的，因为有时间图，任何时间子图都必须使用$ω（n^2）$ edge。我们将分析扩展为证明$ \ tilde {o}（n^2/β）$的上限上的任何时间$β$ - addive spanner的大小，这与pologogarithmic因子有关。 最后，我们研究了$ g $的寿命如何，即其独特的时间标签的数量会影响颞扳手的大小和延伸之间的权衡。
A temporal graph is an undirected graph $G=(V,E)$ along with a function that assigns a time-label to each edge in $E$. A path in $G$ with non-decreasing time-labels is called temporal path and the distance from $u$ to $v$ is the minimum length (i.e., the number of edges) of a temporal path from $u$ to $v$. A temporal $α$-spanner of $G$ is a (temporal) subgraph $H$ that preserves the distances between any pair of vertices in $V$, up to a multiplicative stretch factor of $α$. The size of $H$ is the number of its edges. In this work we study the size-stretch trade-offs of temporal spanners. We show that temporal cliques always admit a temporal $(2k-1)-$spanner with $\tilde{O}(kn^{1+\frac{1}{k}})$ edges, where $k>1$ is an integer parameter of choice. Choosing $k=\lfloor\log n\rfloor$, we obtain a temporal $O(\log n)$-spanner with $\tilde{O}(n)$ edges that has almost the same size (up to logarithmic factors) as the temporal spanner in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then consider general temporal graphs. Since $Ω(n^2)$ edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that $\tilde{O}(n/\log(1+\varepsilon))$ edges suffice to obtain a stretch of $(1+\varepsilon)$, for any small $\varepsilon>0$. This result is essentially tight since there are temporal graphs for which any temporal subgraph preserving exact distances from a single-source must use $Ω(n^2)$ edges. We extend our analysis to prove an upper bound of $\tilde{O}(n^2/β)$ on the size of any temporal $β$-additive spanner, which is tight up to polylogarithmic factors. Finally, we investigate how the lifetime of $G$, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner.
