SCIENCE@home

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

Vincent Cohen-Addad,Arnold Filtser,P. Klein,Hung Le

Published 2020 in IEEE Annual Symposium on Foundations of Computer Science

ABSTRACT

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).

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-76 of 76 references · Page 1 of 1

CITED BY

Showing 1-38 of 38 citing papers · Page 1 of 1