Approximation Schemes for Routing Problems in Minor-Free Metrics
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:
_ Construction of a \emph{light} subset spanner. Given a subset of vertices
called terminals, and $\epsilon$, in polynomial time we construct a subgraph
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.
_ 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))]\le d_G(u,v)+\epsilon D$.
One of our important technical contributions is a novel framework that allows
us to reduce \emph{both problems} to problems on simpler graphs of
\emph{bounded diameter} that we solve using a new decomposition. 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 vehicle routing with bounded capacity in minor-free
metrics; (3) the first efficient approximation scheme for vehicle routing with
bounded capacity on bounded genus metrics.