论文标题
关于远距离图形稀疏的注释
A Note on Distance-Preserving Graph Sparsification
论文作者
论文摘要
我们考虑以下类型的问题：给定图表$ g $，对于最坏的情况，对于稀疏子图$ h $，需要多少个边缘，该子图$ h $大约可以保持给定的节点对$ p $之间的距离？示例包括成对跨度，距离保存器，可及性保留器等。基于击球设定技术的简单结构领域存在趋势，其次是更复杂的结构，这些结构比大约$ \ log log $ ractor从点击集获得的界限改进了界限。在本说明中，我们指出的是，基于击球集的简单构造实际上并不需要额外的$ \ log $因子。这简化并统一了该区域的一些证明，它从$ \ widetilde {o}（np^{2/7}）$ [Kavitha th th。 comp。系统。 '17]至$ o（np^{2/7}）$。
We consider problems of the following type: given a graph $G$, how many edges are needed in the worst case for a sparse subgraph $H$ that approximately preserves distances between a given set of node pairs $P$? Examples include pairwise spanners, distance preservers, reachability preservers, etc. There has been a trend in the area of simple constructions based on the hitting set technique, followed by somewhat more complicated constructions that improve over the bounds obtained from hitting sets by roughly a $\log$ factor. In this note, we point out that the simpler constructions based on hitting sets don't actually need an extra $\log$ factor in the first place. This simplifies and unifies a few proofs in the area, and it improves the size of the $+4$ pairwise spanner from $\widetilde{O}(np^{2/7})$ [Kavitha Th. Comp. Sys. '17] to $O(np^{2/7})$.
