On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
复制标题
DOI：
10.1109/focs46700.2020.00061
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Vincent Cohen-Addad;Arnold Filtser;P. Klein;Hung Le
中科院分区：
文献类型：
--
作者：
Vincent Cohen-Addad;Arnold Filtser;P. Klein;Hung Le
自Robertson和Seymour的基本工作以来，了解无子图度量的结构，即在不包括固定子图的加权图上获得的最短路径度量，一直是一个重要的研究方向。一个基本的想法，既有助于理解这些指标的结构特性，并导致强大的算法结果是构建一个“小复杂度”的图，近似保持度量的点对之间的距离。我们给出了以下两个无次项度量的结构结果：1）构造一个轻子集;给定一个称为终端的顶点子集，和$\n $，在多项式时间内，我们构造一个子图，该子图保持终端之间的所有成对距离，直到一个乘法的$1+\n $因子，其总重量至多为$O_{\displaystyle}（1）$乘以生成终端的最小Steiner树的重量。2)构造嵌入到具有期望加性失真$\xDD $的低树宽图中的随机度量。也就是说，给定一个直径为D的无次图G=（V，E，w），参数为\n，我们构造了一个在树宽为O_{\displaystyle O_{\mathcal{D}}（\log n）的图上的支配度量嵌入分布，使得对于V中的所有u，v，\ \mathbb{E}_{f\sim \mathcal{D}}[d_{H}（f（u），f（v））]\leq d_{G}（u，v）+\xDD $。我们的研究结果具有以下算法的结果：（1）第一次有效的近似方案的子集TSP在次要的自由度量;（2）第一次有效的近似方案的有界容量的车辆路径在次要的自由度量;（3）第一次有效的近似方案的有界亏格度量的有界容量的车辆路径。在途中，后者的结果，我们设计的第一FPT近似方案的有界树宽图（参数化的树宽）上的有界容量的车辆路径。
Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1)Construction of a light subset spanner. Given a subset of vertices called terminals, and $\epsilon$, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative $1+\epsilon$ factor, of total weight at most $O_{\epsilon}(1)$ times the weight of the minimal Steiner tree spanning the terminals. 2)Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion $\epsilon D$. Namely, given a minor-free graph $G= (V, E, w)$ of diameter $D$, and parameter $\epsilon$, we construct a distribution $\mathcal{D}$ over dominating metric embeddings into treewidth-$O_{\epsilon}(\log n)$ graphs such that $\forall u, v\in V,\ \mathbb{E}_{f\sim \mathcal{D}}[d_{H}(f(u), f(v))]\leq d_{G}(u, v)+\epsilon D$. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth).