Additive spanners and (α, β)-spanners

An (α, β)-spanner of an unweighted graph <i>G</i> is a subgraph <i>H</i> that distorts distances in <i>G</i> up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2<i>k</i>−1, 0)-spanner of size <i>O</i>(<i>n</i>^1+1/<i>k</i>) and an (additive) (1,2)-spanner of size <i>O</i>(<i>n</i>^3/2). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size <i>O</i>(<i>n</i>^4/3). The construction algorithm can be understood as an economical agent that assigns <i>costs</i> and <i>values</i> to paths in the graph, <i>purchasing</i> affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this <i>path buying</i> algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any <i>k</i>, a (<i>k</i>,<i>k</i>−1)-spanner with size <i>O</i>(<i>kn</i>^1+1/<i>k</i>) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

无向图\(G\)的\((\alpha,\beta)\)-生成子图是一个子图\(H\)，它使\(G\)中的距离扭曲至多为一个乘法因子\(\alpha\)和一个加法项\(\beta\)。众所周知，任何图都包含一个大小为\(O(n^{1 + 1/k})\)的（乘法）\((2k - 1,0)\)-生成子图和一个大小为\(O(n^{3/2})\)的（加法）\((1,2)\)-生成子图。然而，目前还不知道是否存在其他加法生成子图。 在本文中，我们开发了几种构建\((\alpha,\beta)\)-生成子图的新技术。我们的第一个结果是一个大小为\(O(n^{4/3})\)的加法\((1,6)\)-生成子图。该构建算法可以理解为一个经济主体，它为图中的路径分配成本和价值，购买负担得起的路径并忽略昂贵的路径，而昂贵的路径在直观上可以由已经购买的路径很好地近似。我们表明，这种路径购买算法可以通过不同的方式进行参数化，以产生其他稀疏度 - 失真权衡。我们的第二个结果解决了哪些\((\alpha,\beta)\)-生成子图可以高效计算的问题，理想情况下是在线性时间内。我们表明，对于任何\(k\)，一个大小为\(O(kn^{1 + 1/k})\)的\((k,k - 1)\)-生成子图可以在线性时间内找到，并且进一步地，在分布式网络中，该算法在常数轮数内终止。以前具有类似性能的生成子图构建方法的乘法失真大约是其两倍。