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

arXiv: https://arxiv.org/abs/2009.05039 · HTML: https://mlsanity.com/paper/2009.05039/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2020.

## Built on by (most cited first, 3 of 3)

- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Cobalt: Optimizing Mining Rewards in Proof-of-Work Network Games](https://mlsanity.com/paper/2307.04695/) (2023)
- [NCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2604.16581/) (2026)

## Abstract (arXiv)

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 ε, in polynomial time we construct a subgraph that preserves all pairwise distances between terminals up to a multiplicative 1+ε factor, of total weight at most Oε(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 ε D. Namely, given a minor free graph G=(V,E,w) of diameter D, and parameter ε, we construct a distribution D over dominating metric embeddings into treewidth-Oε(log n) graphs such that the additive distortion is at most ε D. One of our important technical contributions is a novel framework that allows us to reduce both problems to problems on simpler graphs of bounded diameter. 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.