Polynomial-Time
Approximation Schemes for k-Center and Bounded-Capacity
Vehicle Routing in Graphs with Bounded Highway Dimension

arXiv:1707.08270v5 [cs.DS] 13 Nov 2017

Amariah Becker∗,§ , Philip N. Klein†,§ , David Saulpic‡,§

Abstract
The concept of bounded highway dimension was developed to capture observed properties of
the metrics of road networks. We show that a graph with bounded highway dimension, for any
vertex, can be embedded into a a graph of bounded treewidth in such a way that the distance
between u and v is preserved up to an additive error of  times the distance from u or v to the
selected vertex. We show that this theorem yields a PTAS for Bounded-Capacity Vehicle
Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot
and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours,
where each client is visited by some tour and each tour covers at most Q units of client demand.
Our PTAS can be extended to handle penalties for unvisited clients.
We extend this embedding result to handle a set S of distinguished vertices. The treewidth
depends on |S|, and the distance between u and v is preserved up to an additive error of  times
the distance from u and v to S.
This embedding result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle
Routing: the tours can go from one depot to another. The embedding result also implies that, for
fixed k, there is a PTAS for k-Center in graphs of bounded highway dimension. In this problem,
the goal is to minimize d such that there exist k vertices (the centers) such that every vertex is within
distance d of some center. Similarly, for fixed k, there is a PTAS for k-Median in graphs of bounded
highway dimension. In this problem, the goal is to minimize the sum of distances to the k centers.

∗

Department of Computer Science, Brown University. Email: amariah becker@brown.edu
Department of Computer Science, Brown University. Email: klein@brown.edu
‡
Département d’Informatique, École Normale Supérieure, Paris. Work done while visiting Brown University. Email:
david.saulpic@ens.fr
§
Research supported by National Science Foundation grant CCF-1409520.
†

0

1

INTRODUCTION

1

1

Introduction

The notion of highway dimension was introduced by Abraham et al. [3, 1] to explain the efficiency
of some shortest-path heuristics. The motivation of this parameter comes from the work of Bast et
al. [11, 12] who observed that, on a road network, a shortest path from a compact region to points
that are far enough must go through one of a small number of nodes. They experimentally showed
that the US road network has this property. Abraham et al. [3, 1, 2] proved results on the efficiency
of shortest-path heuristics on graphs with bounded highway dimension.
For r ∈ R+ and v ∈ V , Bv (r) = {u ∈ V |d(u,v) ≤ r} denotes the ball with center v and radius r. The
definition of highway dimension we use is from [19]. Let c be a constant greater than 4.
Definition 1. The highway dimension of a graph G is the smallest integer η such that for every r ∈ R+
and v ∈ V , there is a set of at most η vertices in Bv (cr) such that every shortest path in Bv (cr) of
length at least r intersects this set.
(See Section A for more on defining highway dimension.)

1.1

New polynomial-time approximation schemes

Abraham et al. note that “conceivably, better algorithms for other [optimization] problems can be
developed and analyzed under the small highway dimension assumption.” Since some road networks
are described by graphs of small highway dimension, NP-hard optimization problems that arise in
road networks are natural candidates for study. Feldmann [18] and Feldmann, Fung, Könemann,
and Post [19] inaugurated this line of research, giving (respectively) a constant-factor approximation
algorithm for one problem and quasi-polynomial-time approximation schemes for several other problems. In this paper, we give the first polynomial-time approximation schemes (PTASs) for classical
optimization problems in graphs of small highway dimension.
Vehicle routing
Consider Capacitated Vehicle Routing, defined as follows. An instance consists of a positive
integer Q (the capacity), a graph with edge-lengths, a subset Z of vertices (called clients), a demand
function ρ : Z → [1,2...,Q], and a distinguished vertex, called the depot. A solution consists of a set
of tours, where each tour is a path starts and ends at the depot, and a function that assigns each client
to a tour that passes through it, such that the total client demand assigned to each tour is at most
Q. (If a client v is assigned to a tour, we say that the tour visits v.) The objective is to minimize the
sum of lengths of the tours.
We emphasize that in this version of Capacitated Vehicle Routing, client demand is indivisible:
a client’s entire demand must be covered by a single tour. For arbitrary metrics, the problem is
APX-hard, even when Q > 0 is fixed [9]. When Q is unbounded, it is NP-hard to approximate to within
a factor of 1.5 even when the metric is that of a star [21]. Since stars have highway dimension one, this
hardness result holds for graphs of bounded highway dimension. We therefore require Q to be constant.
To emphasize this, we sometimes refer to the problem as Bounded-Capacity Vehicle Routing.
Theorem 1. For any  > 0, η > 0 and Q > 0, there is a polynomial-time algorithm that, given an
instance of Bounded-Capacity Vehicle Routing in which the capacity is Q and the graph has
highway dimension η, finds a solution whose cost is at most 1+ times optimum.
Note that the running time is bounded by a polynomial whose degree depends on ε, η, and Q. As
we discuss in Section 1.3, polynomial-time approximation schemes for vehicle routing were previously
known only for Euclidean spaces. (A quasi-polynomial-time approximation scheme was known for
planar graphs.)

1

INTRODUCTION

2

Our approach can be modified to handle a generalization in which an instance also specifies a penalty
for each client; the solution is allowed to omit some clients and the goal is to find a solution that minimizes
the sum of costs plus penalties. We call this Capacitated Vehicle Routing with Penalties.
As we state in Theorem 5, we give a PTAS for a more general version of the problem, MultipleDepot Bounded-Capacity Vehicle Routing, in which there are a constant number of depots,
and each tour is required only to start and end at one of the depots.
k-Center and k-Median
Next, consider k-Center and k-Median problems. Given a graph, the goal in k-Center is to select
a set of k vertices (the centers) so as to minimize the maximum distance of a vertex to the nearest
center. This problem might arise, for example, in selecting locations for k firehouses. The objective
in k-Median is to minimize the average vertex-to-center distance.
For k-Center, when the number k of centers is unbounded, for any δ > 0, it is NP-hard [22, 29]
to obtain a (2 − δ)-approximation, even in the Euclidean plane under L1 or L∞ metrics,1 even in
unweighted planar graphs [34], and even in n-vertex graphs with highway dimension O(log2 n) [18].
It is not yet known to be NP-hard in graphs with constant highway dimension, but Feldmann [18]
shows that, under the Exponential Time Hypothesis, the running time of an algorithm achieving a
(2−δ)-approximation would be doubly exponential in a polynomial in the highway dimension.
These negative results suggest considering the problem in which k is bounded by a constant. However,
Feldmann [18] shows that (2−)-approximation is W [2] hard for parameter k, suggesting that the
running time of any such approximation algorithm would not be bounded by a polynomial whose degree
is independent of k. Thus even for constant k, finding a much better approximation seems to require
that we restrict the metric. Feldmann [18] gave a polynomial-time 3/2-approximation algorithm for
bounded-highway-dimension graphs, and raised the question of whether a better approximation ratio
could be achieved. The following theorem answers that question.
Theorem 2. There is a function f (·,·,·) and a constant c such that, for each of the problems k-Center
and k-Median, for any η > 0,k > 0 and ε > 0, there is an f (η,k,ε)nc algorithm that, given an instance
in which the graph has highway dimension at most η, finds a solution whose cost is at most 1+ε times
optimum.
Note that the running time is bounded by a polynomial in n whose degree does not depend on η, k, or ε.

1.2

New metric embedding results

The key to achieving the new approximation schemes is a new result on metric embeddings of boundedhighway-dimension graphs into bounded-treewidth graphs. (Treewidth, defined in Section 2, is a
measure of how complicated a graph is, and many NP-hard optimization problems in graphs become
polynomial-time solvable when the input is restricted to graphs of bounded treewidth.)
A metric embedding of an (undirected) guest graph G into a host graph H (or, more generally, metric
space) is a mapping φ(·) from the vertices of G to the vertices of H such that, for every pair of vertices
u,v in G, the φ(u)-to-φ(v) distance in H resembles the u-to-v distance in G. Usually in studying metric
embeddings one seeks an embedding that preserves u-to-v distance up to some factor (the distortion).
That is, the allowed error is proportional to the original distance. In this work, the allowed error is
instead proportional to the distance from a given root vertex (or a constant number of vertices).
Theorem 3. There is a function f (·,·) such that, for every ε > 0 graph G of highway dimension η,
and vertex s, there exists a graph H and an embedding φ(·) of G into H such that
• H has treewidth at most f (ε,η), and
1

Approximation better than 1.822 is hard under L2 , see [17].

1

INTRODUCTION

3

• for all vertices u and v,
dG (u,v) ≤ dH (φ(u),φ(v)) ≤ dG (u,v)+ε(dG (s,u)+dG (s,v))
We give a polynomial-time algorithm that, given the graph G, constructs H and the embedding
of G into H.
every
As we describe in greater detail in Section 5, our PTAS for Bounded-Capacity Vehicle Routing
first applies Theorem 3 with s being the depot and 0 = /c for a constant c to be determined, obtaining
an embedding of the original graph into the bounded-treewidth graph H. The embedding induces
an instance of Vehicle Routing in H. The algorithm finds an optimal solution to this instance,
and converts it to a solution for the original instance. This conversion does not increase the cost of the
solution. However, we need to show that the optimal solution in the original instance induces a solution
in H of not too much greater cost. We do this using a lower bound due to Haimovich and Rinnoy Kan [27].
For the multiple-depot version of vehicle routing and for k-Center and k-Median, Theorem 3
does not suffice. We present a generalization in which there is a set of root vertices, and the allowed
error is proportional to the minimum distance to any root vertex.
Theorem 4. There is a function f (·,·,·) such that, for every ε > 0, graph G of highway dimension
η and set S of vertices of G, there exists a graph H and an embedding φ(·) of G into H such that
• H has treewidth f (η,|S|,ε), and
• for all vertices u and v,
dG (u,v) ≤ dH (φ(u),φ(v)) ≤ (1+O(ε))dG (u,v)+εmin(dG (S,u),dG (S,v))

1.3

Related Work

Metric embeddings of bounded-highway-dimension graphs
As mentioned in Section 1.1, Feldmann [18] and Feldmann et al. [19] inaugurated research into approximation algorithms for NP-hard problems in bounded-highway-dimension graphs. We discuss the work
of Feldmann [19] soon. Feldmann et al. [19] discovered quasi-polynomial-time approximation schemes
for Traveling Salesman, Steiner Tree, and Facility Location. The key to their results is a
probabilistic metric embedding of bounded-highway dimension graphs into graphs of small treewidth.
The aspect ratio of a graph with edge-lengths is the ratio of the maximum vertex-to-vertex distance
to the minimum vertex-to-vertex distance. Feldmann et al. show that, for any  > 0, for any graph G
of highway dimension η, there is a probabilistic embedding φ(·) of G of expected distortion 1+ into a
randomly chosen graph H whose treewidth is polylogarithmic in the aspect ratio of G (and also depends
on  and η). There are two obstacles to using this embedding in achieving approximation schemes:
• The distortion is achieved only in expectation. That is, for each pair u,v of vertices, the expected
φ(u)-to-φ(v) distance in H is at most (1+) times the u-to-v distance in G.
• The treewidth depends on the aspect ratio of G, so is only bounded if the aspect ratio is bounded.
The first is an obstacle for problems (e.g. k-Center) where individual distances need to be bounded;
this does not apply to problems such as Traveling Salesman or Vehicle Routing where the
objective is a sum of lengths of paths. The second is the reason that Feldmann et al. obtain only quasipolynomial-time approximation schemes; it seems to be an obstacle to obtaining true polynomial-time
approximation schemes.
Nevertheless, the techniques introduced by Feldmann et al. are at the core of our embedding results.
We build heavily on their framework.

1

INTRODUCTION

4

Vehicle routing
Haimovich and Rinnoy Kan [27] proved the following lower bound2 :
Lemma 1. For Capacitated Vehicle Routing with capacity Q, and client set Z,
2X
{d(c,s) : c ∈ Z}
cost(OPT) ≥
Q
Note that the Capacitated Vehicle Routing problem, is a generalization of Traveling Salesman (Q = n, Z = V , and ρ(v) = 1,∀v). Conversely, Haimovich and Rinnoy Kan show how to use a
solution to Traveling Salesman to achieve a constant-factor approximation for Capacitated Vehicle Routing, where the constant depends on the approximation ratio for Traveling Salesman.
Since Capacitated Vehicle Routing in general graphs is APX-hard for every fixed Q ≥ 3 [8, 9],
much work has focused on the Euclidean plane. Haimovich and Rinnoy Kan [27] gave a polynomial-time
approximation scheme (PTAS) for the Euclidean plane for the case when the capacity Q is constant.
Asano et al. [9] showed how to improve this algorithm to get a PTAS when Q is O(logn/loglogn).
For general capacities, Das and Mathieu [16] gave a quasi-polynomial-time approximation scheme
for unbounded Q. Building on this work, Adamaszek, Czumaj, and Lingas [4] gave a PTAS that for
δ
any  > 0 can handle Q up to 2log n where δ depends on .
Little is known for higher dimensions or other metrics. Kachay gave a PTAS in Rd that requires Q to
be O(log1/d logn) [32], and Hamaguchi and Katoh [28] and Asano, Katoh, and Kawashima [7] focused
on constant-factor approximation algorithms for the case where the graph is a tree and client demand
is divisible. Becker, Klein and Saulpic [13] gave the first approximation scheme for a non-Euclidean
metric: they describe a quasi-polynomial-time approximation scheme in planar graphs, but only when
the capacity Q is polylogarithmic in the graph size. They introduce the idea of an error that depends
on the distance to the depot, which we also use in the embedding presented in our work here.
k-Median
We have already surveyed some of the results on k-Center. Note that the results of Feldmann [18] are
based on the definition of highway dimension of 2011 [1], but can be adapted to the definition we use here.
For k-Median, constant-factor approximation algorithms have been found for general√metric
spaces [35, 30, 6]. The best known approximation ratio for k-Median in general metrics is 1+ 3 [33],
and it is NP-hard to approximate within a factor of 1 + 2/e [23]. For k-Median in d-dimensional
Euclidean space, PTAS have been found when k is fixed (e.g. [10]) and when d is fixed (e.g. [5]) but
there exists no PTAS if k and d are part of the input [26]. Recently Cohen-Addad et al. [14] gave a
local search-based PTAS for k-Median in edge-weight planar graphs that extends more generally
to minor-closed graph families.

1.4

Paper Outline

Section 2 provides preliminary definitions and presents useful results from Feldmann et al. [19]. In
Section 3 we give a first embedding result, that concerns graphs of bounded aspect ratio. Section 4
explains the second embedding result (Theorem 3) and Section 5 presents how to use it to achieve
a PTAS for Capacitated Vehicle Routing, proving Theorem 1. Section 6 describes the dynamic
program used for Capacitated Vehicle Routing, and finally Section 7 gives the third embedding
result (Theorem 4) and applies it to several problems.
2

Although their result addresses the unit-demand case, it generalizes to instances where all non-zero client demand
ρ(v) is at least one for every client v ∈ Z.

2

PRELIMINARIES

2

5

Preliminaries

We use OP T to denote the optimum solution for an optimization problem. For minimization problems,
an α-approximation algorithm returns a solution with cost at most α·cost(OP T ). An approximation scheme is a family of (1 + ε)-approximation algorithms indexed by ε > 0. A polynomial-time
approximation scheme (PTAS) is an approximation scheme that for each ε runs in polynomial time.
For an undirected graph G = (V,E), we use dG (u,v) (or d(u,v) when G is unambiguous) to denote
the shortest-path distance between u and v. For any vertex subsets W ⊆ V and vertex v ∈ V we let
d(v,W ) denote minw∈W d(v,w), and we let diam(W ) denote maxu,v∈W d(u,v).
An embedding of a graph G = (V,E) is a mapping φ from a guest graph G to a host graph H = (V,EH ).
For notational simplicity, we identify the vertices of H with points of G and therefore omit φ.
A tree decomposition of a graph G is a tree TG whose nodes are bags of vertices that satisfy the
following three criteria:
1. Every v ∈ V appears in at least one bag.
2. For every edge (u,v) ∈ E there is some bag containing both u and v.
3. For every v ∈ V , the bags containing v form a connected subtree.
The width of TG is the size of the largest bag minus one. The treewidth of G is the minimum width
among all tree decompositions of G. It is a measure of how treelike a graph is. Observe that the
treewidth of a tree is one. Tree decompositions are useful for dynamic-programming algorithms, but
often give runtimes that are exponential in the treewidth. Therefore many problems that are N P -hard
in general can be solved efficiently in graphs of bounded treewidth.
Let Y ⊆ X be a subset of elements in a metric space (X,d). Y is a δ-covering of X if for all x ∈ X,
d(x,Y ) ≤ δ. Y is a β-packing of X if for all y1 ,y2 ∈ Y with y1 6= y2 , d(y1 ,y2 ) ≥ β. Y is an ε-net if it is
both an ε-covering and an ε-packing.

2.1

Shortest-Path Covers

Instead of working directly with Definition 1, we use the concept of a shortest-path cover, which as
noted in Abraham et al. [1] is a closely related and more convenient tool.
Recall that c is a constant greater than 4.
Definition 2. For a graph G with vertex set V and r ∈ R+ , a shortest-path cover SPC(r) ⊆ V is a
set of hubs such that every shortest path of length in (r, cr/2] contains at least one hub from this set.
Such a cover is called locally s-sparse for scale r if every ball of diameter cr contains at most s vertices
from SPC(r).
For a graph of highway dimension η, Abraham et al. [1] showed how to find a ηlogη-sparse shortestpath cover in polynomial time (though they show it for a different definition of highway dimension
(c = 4), the algorithm can be straightforwardly adapted). This result justifies using shortest-path
covers instead of directly using highway dimension.

2.1.1

Town Decomposition

Feldmann et al.[19] observed that a shortest-path cover for scale r naturally defines a clustering of the
vertices into towns [19]. Informally, a town at scale r is a subset of vertices that are close to each other
and far from other towns and from the shortest-path cover for scale r. Formally, a town is defined
by at least one v ∈ V such that d(v,SPC(r)) > 2r and is composed of {u ∈ V |d(u,v) ≤ r}.
Lemma 2 describes key properties of towns proved in Feldmann et al and depicted in Figure 1.
Lemma 2 (Lemma 3.2 in [19]). If T is a town at scale r, then

2

PRELIMINARIES

6

1. diam(T ) ≤ r and
2. d(T,V \T ) > r
Proof. See Appendix B for proof sketch.

Figure 1: Illustration of Lemma 2
Feldmann et al. define a recursive decomposition of the graph using the concept of towns, which
we adopt for this paper. First, scale all distances so that the shortest point-to-point distance is a little
more than c/2. Then fix a set of scales ri = (c/4)i . We say that a town T at scale ri is on level i. Remark
that the scaling ensures that SP C(r0 ) = ∅, and therefore at level 0 every vertex forms a singleton
town. Also note that the largest level is rmax = dlogc/4 diam(Gscaled )e = dlogc/4 ( 2c ·θG ))e, where θG is
the aspect ratio of the input graph. Similarly at this topmost level, SP C(rmax ) = ∅ since there are
no shortest paths that need to be covered. The only town at scale rmax is the town that contains the
entire graph. We say that the town at scale rmax and the singleton towns at scale r0 are trivial towns.
Since c is a constant greater than four, the total number of scales is linear in the input size.
Consider the set T = {T ⊆ V |T is a town on level i ∈ N} of towns for all levels. Because of the
properties of Lemma 2, this set forms a laminar family and therefore has a tree structure. Towns on the
same level are disjoint from each other. By the isolation property of the town (the second property of
Lemma 2), vertices outside of a town must be far from the town, so a smaller town cannot be both inside
and outside of a larger town. Indeed, if two towns intersect, then the smaller town must be entirely
inside the bigger (see [19] for more details). Moreover, the decomposition has the following properties:
Lemma 3 (Lemma 3.3 in [19]). For every town T in a town decomposition T ,
1. T has either 0 children or at least 2 children, and
2. if T is a town at level i and has child town T 0 at level j, then j < i.
Proof. See Appendix B for proof sketch.
The set T is called the town decomposition of G, with respect to the shortest-path cover, and is
a key concept used in this paper.
2.1.2

Approximate Core Hubs

Another insight that we adopt from Feldmann et al. is that rather than working with all hubs in
the shortest-path covers, it is sufficient for approximation algorithms to retain only a representative
subset of the hubs: for T
ε > 0, Feldmann et al. define for each town T a set XT of approximate core hubs
which is a subset of T
∪i SPC(ri ) with the properties described in Lemma 4. One key property of
these sets is a bound on their doubling dimension. The doubling dimension of a metric is the smallest
θ such that for every r, every ball of radius 2r can be covered by at most 2θ balls of radius r.
Lemma 4 (Theorem 4.2 and Lemma 5.1 in [19]). Let G be a graph of highway dimension η, and T
be a town decomposition with respect to an inclusion-wise minimal, s-sparse shortest-path cover. For
any town T ∈ T ,

3

EMBEDDING FOR GRAPHS OF BOUNDED DIAMETER

7

1. if T1 and T2 are different child towns of T , and u ∈ T1 and v ∈ T2 , then there is some h ∈ XT such
that d(P [u,v],h) ≤ εd(u,v), where P [u,v] is the shortest u-to-v path, and
2. the doubling dimension of XT is θ = O(log(ηslog(1/ε)).
Intuitively, the shortest-path cover at scale ri forms a set of points that covers exactly the shortestpaths of length in (ri ,ri+1 ]. Therefore to cover the shortest-path between u ∈ T1 and v ∈ T2 , we can
use a hub at level j such that d(u,v) ∈ (rj ,rj+1 ]. Unfortunately, taking all the shortest-path covers
gives a set too big for our purpose. But since we want to cover approximately the distances between
points in different child towns, we can take only a subset of the shortest-path covers that has a low
doubling dimension. This subset can be found in nO(1) time as explained in Feldmann et al. [19].
2.1.3

Minimality of Shortest-Path Covers

Note that the result of Lemma 4 requires the shortest-path covers be inclusion-wise minimal. For
the embedding we present in Section 4, however, it is useful to assume that the depot is not a member
of any town except for the trivial topmost town containing all of G and bottommost singleton town
containing just the depot. One way to ensure this is to add the depot to the shortest-path cover at every
level, but this violates the minimality requirement (see Appendix C for further discussion). Lemma 5,
however, shows that this assumption can be made safely without asymptotically changing our results.
We prove a more general statement for a set S of depots. Recall that c is a constant greater than four
and that all edges have been scaled so that the smallest point-to-point distance is slightly more than c/2.
Lemma 5. Any graph G = (V,E) with highway dimension η, diameter ∆G , and designated vertex set
S ⊆ V can be modified by adding O(η 2 |S|3 log∆G ) new vertices and edges, such that the resulting graph
G0 = (V 0 ,E 0 )
• has highway dimension at most η+|S|
• for all u,v,∈ V 0 , dG0 (u,v) ∈ ( 2c ,

3c
4 ∆G ]

• for all u,v ∈ V , dG0 (u,v) = dG (u,v), and
• for every s ∈ S, the only towns containing s in the town decomposition of G0 are the trivial towns.
Proof. See Appendix C.
Note that after applying the modification of Lemma 5 to the (scaled) input graph, the resulting
graph has size that is polynomial in the size of the original input.

3

Embedding for Graphs of Bounded Diameter

Lemma 6 describes an embedding for the case when the graph has bounded diameter. This embedding
gives only a small additive error, and will prove to be a useful tool for the following sections. In this
section we show how to construct this embedding.
Lemma 6. There is a function f (x,y) such that, for any ε > 0 and η > 0, for any graph G with
highway dimension at most η and diameter ∆, there is a graph H with treewidth at most f (ε,η) and
an embedding φ(·) of G into H such that, for all points u and v,
dG (u,v) ≤ dH (φ(u),φ(v)) ≤ dG (u,v)+4ε∆
Furthermore, there is a polynomial-time algorithm to construct H and the embedding.
We first present an algorithm to compute the host graph H and a tree decomposition of H. This
algorithm relies on the town decomposition T of G, described in Section 2.
The host graph H is constructed as follows. First, consider a town T that has diameter d ≤ ε∆ but has
no ancestor towns of diameter ε∆ or smaller. We call such a town a maximal town of diameter at most

3

EMBEDDING FOR GRAPHS OF BOUNDED DIAMETER

(a) Town decomposition

(b) Embeddings

8

(c) Path approximation

Figure 2: (a) An example town decomposition. T1 has diameter at most ε∆ and T2 has diameter
greater than ε∆. (b) Two cases of town embeddings. T1 is embedded as a star with center vT1 . The
embedding of T2 connects all vertices in T2 to all hubs in X̂T2 (depicted as squares). (c) Hub ĥ ∈ X̂T
is close to hub h ∈ XT which itself is close to the shortest u-to-v path.
ε∆. The town T is embedded into a star: choose an arbitrary vertex vT in T , and for each u ∈ T , include
an edge in H between u and vT with length dG (u,vT ) equal to their distance in G (see Figures 2a and 2b).
Now consider a town T of diameter dT > ε∆. The set of approximate core hubs XT can be used as portals to preserve distances between vertices lying in different child towns of T . Specifically, by Lemma 4,
for every pair of vertices (u,v) in different child towns of T , XT contains a vertex that is close to the shortest path between u and v. In order to approximate the shortest paths, it is therefore sufficient to consider
a set of points close to XT . Let X̂T be an εdT -net of XT . For each ĥ ∈ X̂T and v ∈ T , include an edge in H
connecting v to ĥ with length dH (v,ĥ) = dG (v,ĥ) equal to the v-to-ĥ distance in G (see Figures 2a and 2b).
The tree decomposition D mimics the town decomposition tree: for each town T of diameter greater
than ε∆, there is a bag bT . This bag is connected in D to all of the bags of child towns of T and
contains all of the vertices of the net assigned to T and of the nets assigned to T ’s ancestors
in the town
S
decomposition. Formally, if AT denotes the set of all towns that contain T , bT = T 0 ∈AT X̂T 0 . Note
that if T 0 is the parent of T in the town decomposition, bT = X̂T ∪bT 0 . Now for each maximal town
T of diameter at most ε∆ with parent town T 0 , the tree decomposition contains a bag b0T connected
to a bag buT for each vertex u ∈ T . We define b0T = {vT }∪bT 0 and buT = {u}∪b0T .
Following Feldmann et al. [19], the above construction can be shown to be polynomial-time
constructible. The following three lemmas therefore prove Lemma 6.
Lemma 7. D is a valid tree decomposition of H.
Proof. For D to be a valid tree decomposition of H, it has to satisfy the three criteria listed in the
preliminaries.
As every vertex v is in some maximal town T of diameter at most ε∆ (because every vertex form a
singleton town at level 0), there is a leaf bvT of D that contains v. Moreover, this leaf contains all of the vertices adjacent to v in H: if an edge connects u and v, then either u or v is the center of the star for T , or u is
in the net of some town that contains v. In both cases the construction of D ensure that u is in bvT . Finally,
let T be a town such that bT is the highest bag in the tree decomposition that contains v. As the towns
at a given height of the town decomposition form a partition of the vertices, this town is unique. Since
the town decomposition has a laminar structure, v cannot appear in a bag that is not a descendant of bT .
Furthermore, by definition of the bags, v appears in all descendants of bT , proving the third property.
Lemma 8. H has a treewidth O(( 1ε )θ log c 1ε ), where θ is a bound on the doubling dimension of the sets
4
XT .

4

MAIN EMBEDDING

9

Proof. Since the size of the bags is clearly bounded by the depth times the maximal cardinality of X̂T ,
it is enough to prove that, for each town T , X̂T is bounded by ( 1ε )θ , and that the tree decomposition
has a depth O(log c 1ε ).
4

By Lemma 4, the doubling dimension of XT is bounded by θ. X̂T is a subset of XT , so its doubling
dimension is bounded by 2θ (see Gupta et al. [24]). Furthermore, the aspect ratio of X̂T is 1ε : the
longest distance between members of X̂T is bounded by the diameter dT of the town, and the smallest
distance is at least εdT by definition of a net. The cardinality of a set with doubling dimension x and
aspect ratio γ is bounded by 2xdlog2 γe (see [25] for a proof), therefore |X̂T | is bounded by ( 1ε )θ .
We prove now that the tree decomposition has a depth O(log c 1ε ). Let T be a town of diameter
4
dT > ε∆ and let ri be the scale of that town. By Lemma 2, dT ≤ ri , and since ri = ( 4c )i and dT > ε∆,
we can conclude that i > log c ε∆. As the diameter of the graph is ∆, the biggest town has a diameter
4
at most ∆. It follows that ri ≤ ∆ and therefore i ≤ log c ∆. The depth of bT in the tree decomposition
4

∆
is therefore bounded by log c ε∆
= log c 1ε . Furthermore, the tree decomposition of a town of diameter
4
4
at most ε∆ has depth 2. The overall depth is therefore O(log c 1ε ), concluding the proof.
4

Lemma 9. For all vertices u and v, dG (u,v) ≤ dH (u,v) ≤ dG (u,v)+4ε∆
Proof. Let u and v be vertices in V , and let T be the town that contains both u and v such that u
and v are in different child towns of T .
If T has diameter dT ≤ ε∆, then let T 0 be the maximal town of diameter at most ε∆ that is an
ancestor of T (possibly T itself). By construction, T 0 was embedded into a star centered at some
vertex vT 0 ∈ T 0 , so dH (u,v) ≤ dH (u,vT 0 )+dH (vT 0 ,v) ≤ dG (u,vT 0 )+dG (vT 0 ,v) ≤ 2ε∆.
Otherwise if T has diameter dT > ε∆, then by Lemma 4, there is some h ∈ XT such that
dG (P [u,v],h) ≤ εd(u,v). Since X̂T is an εdT cover of XT , there is some ĥ ∈ X̂T such that d(h,ĥ) ≤ εdT .
The host graph H includes edges (u,ĥ) and (ĥ,v), so
dH (u,v) ≤ dH (u,ĥ)+dH (ĥ,v) ≤ dG (u,h)+dG (h,v)+2εd(u,v)+2εdT ≤ dG (u,v)+4ε∆ (see Figure 2c).
Finally, since edge lengths in H are given by distances in G, dG (u,v) ≤ dH (u,v) for all u,v ∈ V .
The next sections present some applications of the above embedding.

4

Main Embedding

In this section, we prove Theorem 3, restated here for convenience.
Theorem 3. There is a function f (·,·) such that, for every ˆ > 0 graph G of highway dimension η,
and vertex s, there exists a graph H and an embedding φ(·) of G into H such that
• H has treewidth at most f (ˆ
,η), and
• for all vertices u and v,
dG (u,v) ≤ dH (φ(u),φ(v)) ≤ dG (u,v)+ˆ
(dG (s,u)+dG (s,v))

4.1

Embedding Construction

Given the parameter ˆ, our goal for the embedding is that
dG (u,v) ≤ dH (φ(u),φ(v)) ≤ dG (u,v)+ ε̂(dG (s,u)+dG (s,v))
With this goal in mind, we define  = min{1/4,ε̂/c} for an appropriate constant c, and we prove that
dG (u,v) ≤ dH (φ(u),φ(v)) ≤ dG (u,v)+O(ε)(dG (s,u)+dG (s,v))
The constant c is chosen to compensate for the big-O in the above inequality.

4

MAIN EMBEDDING

10

Our construction relies on the assumption that the depot s does not appear in any non-trivial town.
By Lemma 5 (using S = {s}), this assumption is safe, since the input graph can be modified to satisfy
this assumption without (asymptotically) changing the highway dimension, diameter, or size of the
graph. Furthermore since the modification preserves original distances, and all newly added vertices
can be assumed to have no client demand, the modification does not affect the solution.
The root town in the composition, denoted T0 , is the town that contains the entire graph. We say
that a town T that is a child of the root town is a top-level town, which means that the only town
that properly contains T is T0 .
The assumption that the depot, s, does not appear in any non-trivial town implies that the top-level
town that contains s is the trivial singleton town. This assumption is helpful to bound the distance
between a top-level town T and the depot s: as s ∈
/ T , Lemma 2 gives the bound d(T,s) ≥ diam(T ).
This bound turns out to be very helpful in the construction of the host graph.
We use Lemma 6 to construct an embedding for each top-level town. It remains to connect these
embeddings : we cannot approximate XT0 with a net as we did in Lemma 6, because the diameter
of G may be arbitrarily large.
To cope with that issue, we define inductively the hub sets X00 ,X01 ,... such that X0k is a net of
XT0 ∩Bs (2k ). Let X00 be an ε-net of XT0 ∩Bs (1) that
the depot, s, and for k ≥ 0 let X0k+1 be
 Scontains
k
k+1
k+1
k
an ε2 -net of the set XT0 ∩(Bs (2 )−Bs (2 ))
X0 that contains the depot. This construction
k+1
k
k
ensures that X0 ∩Bs (2 ) ⊆ X0 , which will be helpful in Section 4.3 to find a tree decomposition
of the host graph. Note that we can assume s ∈ XT0 , since adding it increases the doubling dimension
by at most one and thus does not change the result of Lemma 4.
For a set of vertices X ⊆ V , we define l(X ) = dlog2 (maxv∈X d(s,v))e (See Figure 3a).
For every child town T of T0 , the host graph connects every vertex v of T to every hub h in
l(T )+log2 (1/ε)
l(T )
X0 ,...,X0
with an edge of length dG (v,h) (See Figure 3b).

4.2

Proof of Error Bound

In Lemma 11 we prove a bound on the error incurred by the embedding. Our proof makes use of the
following lemma.
Lemma 10. For all k, X0k is an ε2k+1 -covering of XT0 ∩Bs (2k ).
Proof. We proceed by induction. By construction, X00 is an ε-net (and thus also an ε21 -covering) of
k−1
k ).
XT0 ∩Bs (20 ). Assume that X0k−1 is an ε2k -covering of XT0∩B
S s (2k ), and let x ∈kXT0 ∩Bs (2
k
k
k
k−1
k−1
X0 , so if x ∈ Bs (2 ) − Bs (2 ) then
X0 is an ε2 -net of the set XT0 ∩ (Bs (2 ) − Bs (2 ))
there is a y ∈ X0k such that d(x,y) ≤ ε2k < ε2k+1 . Otherwise x ∈ Bs (2k−1 ). By assumption, there is
an x̂ ∈ X0k−1 such that d(x, x̂) ≤ ε2k , and by construction, there is a y ∈ X0k such that d(y, x̂) ≤ ε2k .
Therefore d(x,y) ≤ ε2k +ε2k = ε2k+1 .
Lemma 11. For all vertices u and v, dG (u,v) ≤ dH (u,v) ≤ dG (u,v)+O(ε)(dG (s,u)+dG (s,v))
Proof. Consider two vertices u and v. Let Tu and Tv denote the top-level towns that contain u and
v, respectively. There are two cases to consider.
If Tu = Tv , Lemma 2 gives dG (u, v) ≤ diam(Tu ) ≤ dG (Tu , V \ Tu ), and therefore diam(Tu ) ≤
min{dG (s,u), dG (s,v)}. Because Tu = Tv is a top-level town, its embedding is given by Lemma 6,
which directly gives the desired bound.
Otherwise Tu 6= Tv . Without loss of generality, assume that dG (u,s) ≥ dG (v,s). We show that there
exists some X0k connected to u with a vertex ĥ ∈ X0k close to P [u,v].
By definition of the approximate core hubs, there exists h ∈ XT0 such that d(h,P [u,v]) ≤ εd(u,v).
Moreover, h ∈ Bs (2l(Tu )+2 ):

4

MAIN EMBEDDING

11

Figure 3: (a) Towns T1 and T2 are top-level towns, with l(T1 ) = i and l(T2 ) = i+1. (b) The embedding
of each top-level town (shown as circles) are connected to a band of log2 1ε + 1 hub sets (shown as
squares). Edges are striped to convey that they connect all vertices of the given hub-set endpoint
to all vertices of the town-embedding endpoint. (c) The vertices of each bag B (shown as circles)
are added to each bag of each descendent top-level-town tree decomposition (shown as triangles).

(a) Towns

(b) Embedding

(c) Tree decomposition

d(s,h)

≤ d(s,u)+d(u,h)
≤ d(s,u)+(1+ε)d(u,v)

≤ d(s,u)+(1+ε) d(s,u)+d(s,v)
≤ d(s,u)+(1+ε)·2d(s,u)
≤ (3+2ε)2l(Tu )
≤ 2l(Tu )+2

by the triangle inequality
since d(u,s) ≥ d(v,s)

l(T )+2

Since h ∈ XT0 ∩Bs (2l(Tu )+2 ), then by Lemma 10, there is an ĥ ∈ X0 u
such that d(ĥ,h) ≤ ε2l(Tu )+3 .
1
Since log2 ε ≥ 2, u is connected to ĥ in the host graph.
Depending on v, there remain two cases: either v is connected to ĥ (see Figure 4a) or not (Figure 4b).
First, if v is connected to ĥ in the host graph, dH (v, ĥ) = dG (v, ĥ) (and the same holds for u). The
triangle inequality gives therefore,
dH (u,v) ≤ dG (u,ĥ)+dG (v,ĥ) ≤
dG (u,h)+dG (v,h)
+
2dG (ĥ,h)
|
{z
}
| {z }
≤(1+2ε)dG (u,v) by definition of h

≤2ε2l(Tu )+3 =O(ε)d(s,u)

Since dG (u,v) ≤ dG (s,u)+dG (s,v), we can conclude that,
dH (u,v) ≤ dG (u,v)+O(ε)(dG (s,u)+dG (s,v))
Otherwise, v is not connected to ĥ. That means that either l(Tu ) + 2 < l(Tv ) or l(Tu ) + 2 >
l(Tv ) + log2 1ε . We exclude the first case by noting that since the diameter of a town is less than
its distance to the depot, dG (v,s) ≤ dG (u,s) implies that l(Tv ) ≤ l(Tu ) + 1. The second case implies that dG (s,u) ≥ O( 1ε )dG (s,v). Since the host graph connects the source s to all the vertices,
dH (u,v) ≤ dG (s,u)+dG (s,v) ≤ dG (u,v)+2dG (s,v) ≤ dG (u,v)+O(ε)(dG (s,u)+dG (s,v)).

4

MAIN EMBEDDING

12

(a) u and v are both connected to ĥ

(b) v is not connected to ĥ

Figure 4: The shortest path between u and v in G is indicated by the curved, directed lines. The
path in the host graph is represented by the straight lines.

4.3

Tree Decomposition

We present here the construction of a tree decomposition D of the host graph with a bounded width.
k+logS
2 (1/ε)
For each k > 0 let Bk =
X0i . For a top-level town T , the tree decomposition D connects the
i=k−1

decomposition DT given by Lemma 6 to the bag Bl(T ) . Moreover, we add all vertices that appear in Bl(T )
to all bags in the tree DT . Finally, for every k we connect Bk to both Bk−1 and Bk+1 in D. (See Figure 3b.)
Lemma 12. D is a valid tree decomposition of the host graph H.
Proof. For D to be a valid tree decomposition of H, it has to satisfy the three properties listed in
Section 2.
First, because the top-level towns are a partition of the vertices, each vertex appears in some tree
decomposition DT . The union of all bags is therefore V (H).
Next, let (u,v) be an edge of H. There are two cases to consider: if u and v are in the same top-level
town, Lemma 6 ensures that u and v appear together in some bag. Otherwise, as the top-level towns
are disjoint, one of u or v is a hub connected to the other. Without loss of generality assume that v
is a hub of X0k for some k ∈ {l(Tu ),...,l(Tu )+log2 1ε }. In this case, v ∈ Bl(Tu ) , so v is added to all the
bags of DTu , and in particular is in some bag that contains u.
Finally, let v be a vertex that appears in two different bags. If the two bags are in the tree
decomposition of the same top-level town T , Lemma 6 ensures that the bags are connected in DT and
thus also in D. Otherwise, as the top-level towns are disjoint, v must be a hub. Consider all nets X0k
containing v. Any bag B` containing such a net also contains v. Let I = {k|v ∈ X0k }. We prove that I is an
interval, and therefore that the bags B` are connected. Let i = min(I) and j = max(I). As v ∈ X0i , it must
be that v ∈ Bs (2i ) ⊆ Bs (2i+1 ) ⊆ ... ⊆ Bs (2j ). Repeatedly applying the property X0k ∩Bs (2k−1 ) ⊆ X0k−1
proves that for all k ∈ {i,i+1,...j}, v ∈ X0k . Therefore I is an interval, and the bags B` such that v ∈ B`
l({v})
are connected. Finally, we show that interval I includes Bl (Tv ). Since v is a hub, v ∈ X0
. By
Lemma 2, d(v,s) > diam(Tv ), so l(Tv )−1 ≤ l({v}) ≤ l(Tv ), and therefore v ∈ Bl (Tv ). Since the vertices
of Bl (Tv ) are added to every bag in DTv , the bags containing v form a connected subtree of D.
Lemma 13. For all k, |X0k | ≤ ( 2ε )θ .

5

CAPACITATED VEHICLE ROUTING

13

Proof. Since X0k is a subset of XT0 , it has doubling dimension 2θ (see Lemma 4). Since X0k is a ε2k -net,
the smallest distance between two hubs in X0k is at least ε2k . Moreover, since X0k ⊆ Bs (2k ), the longest
distance between two hubs is at most 2·2k , therefore, X0k has an aspect ratio of at most 2ε . The bound
used in Lemma 8 on the cardinality of a set using its aspect ratio and its doubling dimension concludes
the proof.
Lemma 14. The tree decomposition D has bounded width.
Proof. Bag Bi is the union of log2 1ε + 2 sets X0k . Lemma 13 gives |X0k | ≤ ( 2ε )θ , therefore |Bi | ≤
(log2 ( 1ε ) + 2)( 2ε )θ . Moreover, by Lemma 8, each bag of the DT decompositions has a cardinality
bounded by O(( 2ε )θ log c 1ε ). Therefore, since each bag of the decomposition D is either a bag Bi for
4
some i or is formed by adding a single bag Bi to some bag of a DT decomposition, its size is bounded.
Therefore D has a bounded width.

5
5.1

Capacitated Vehicle Routing
PTAS for Bounded Highway Dimension

The Capacitated Vehicle Routing problem for some graph G, demand function ρ : V → [1,2,...,Q],
depot vertex s ∈ V and capacity Q > 0 seeks a set of tours of minimal total length that collectively visit
all clients (vertices with positive client demand), such that each tour contains s and covers at most
Q units of client demand. In this section, we apply Theorem 3 to Capacitated Vehicle Routing,
for graphs of bounded highway dimension η and fixed capacity Q.
The algorithm works as follows. The input graph G is embedded into a host graph H of bounded
treewidth using the embedding given in Theorem 3. The algorithm then optimally solves the Capacitated Vehicle Routing problem with capacity Q for H, using the dynamic programming
algorithm given in Section 6. The solution for H is then lifted to a solution in G: for each tour in the
solution for H, a tour in G that visits the same clients in the same order is added to the solution for G.
We show that the embedding given in Theorem 3 is such that an optimal solution in the host graph
H gives a (1 + ε) solution in G. Furthermore, the embedding ensures that H has small treewidth,
allowing Capacitated Vehicle Routing to be solved exactly in polynomial time using dynamic
programing. Putting these together gives Theorem 1, restated here for convenience.
Theorem 1. For any  > 0, η > 0 and Q > 0, there is a polynomial-time algorithm that, given an
instance of Bounded-Capacity Vehicle Routing in which the capacity is Q and the graph has
highway dimension η, finds a solution whose cost is at most 1+ times optimum.
Given an embedding with the properties described in Theorem 3, all that remains in proving
Theorem 1 is showing how to solve Capacitated Vehicle Routing optimally on the host graph
H and proving that such an optimal solution has a corresponding near-optimal solution in G. We
do so in the following two lemmas.
Lemma 15. Given a graph with bounded treewidth ω and a capacity Q > 0, Capacitated Vehicle
Routing can be solved optimally in nO(ωQ) time.
Proof. See Section 6
Lemma 16. For an embedding with the properties given by Theorem 3, the cost of an optimal solution
in the host graph H is within a (1+O(ε))-factor of the cost of the optimal solution in the guest graph G.

6

DYNAMIC PROGRAM FOR CAPACITATED VEHICLE ROUTING

14

Proof. Let OPTH be the optimal solution in the host graph H and OPTG be the optimal solution
in G. A solution is described by the order in which the clients and the depot are visited: (u,v) ∈ S
indicates that the solution S visits the client v immediately after visiting u. We want to prove that
costG (OPTH ) ≤ (1+O(ε))costG (OPTG ).
First, since dG ≤ dH , costG ≤ costH . Second, the solution OPTG is also a solution in the host graph H,
since the vertices of G and H are the same. So, by definition of OPTH , costH (OPTH ) ≤ costH (OPTG ).
It is therefore sufficient to prove that costH (OPT
P G ) ≤ (1+O(ε))costG (OPTG ).
By definition of cost, costH (OPTG ) =
dH (u,v). Applying Theorem 3 gives
(u,v)∈OPTG
X
costH (OPTG ) ≤
dG (u,v)+O(ε)(dG (s,u)+dG (s,v))
(u,v)∈OPTG

The right side of the inequality
can be rewritten as
X
O(ε)
dG (u,v) +
{z

= costG (OPTG )

dG (s,u)+dG (s,v)

(u,v)∈OPTG

(u,v)∈OPTG

|

X

}

|

= O(ε)

P

{z

}

2dG (s,v) ≤ O(ε)QcostG (OPTG ) (∗)

v∈Z

To get the inequalities (∗), it is enough to remark that OPTG visits every client exactly once and
then to apply Lemma 1. As Q is constant, the whole inequality becomes
costH (OPTG ) ≤ costG (OPTG )+O(ε)costG (OPTG ) = (1+O(ε))costG (OPTG )

5.2

Generalization to Routing with Penalties

The Capacitated Vehicle Routing with Penalties is a natural generalization of Capacitated
Vehicle Routing in which a penalty is specified for each client, and the solution can omit some
clients (and pay their penalties). The embedding proposed previously can be used to solve it. First,
the dynamic program for graphs of bounded treewidth can be adapted to solve this problem optimally
in such graphs. The only change to make is that instead of visiting a client, the algorithm can chose to
pay the penalty. It remains to prove that an optimal solution in the host graph is close to an optimal
solution in the guest graph.
Lemma 17. The optimal solution to Capacitated Vehicle Routing with Penalties in the
host graph has a cost at most (1+ε)cost(OPTG )
Proof. The clients can be divided into two sets U and W : the optimal solution in G visits every vertex
in U and pays the penalty for the ones in W . Applying Lemma 1 to the set U , gives the following:
X
2X
cost(OPTG ) ≥
d(v,s)+
p(v)
Q
v∈U
v∈W
With this lower bound, the proof of Lemma 16 can be adapted to handle penalties, giving
costH (OPTG ) ≤ (1 + O(ε))costG (OPTG ). The conclusion is similar to the one of Lemma 16:
costG (OP TH ) ≤ (1+O(ε))costG (OPTG ).

6

Dynamic Program for Capacitated Vehicle Routing

In this section, we present a dynamic program running in nO(ωQ) to solve Capacitated Vehicle
Routing for capacity Q on graphs with treewidth ω. Given a tree decomposition, D, choose an
arbitrary bag to be the root, and for each bag b of the decomposition let cluster Cb be the union of
the bags descending from b in the tree decomposition, minus the elements of b itself. The bag b forms
a boundary between cluster Cb and V \Cb .
A configuration in the dynamic program describes how a solution interacts with a cluster: for each
vertex v in the boundary b of the cluster, and for each possible capacity q ≤ Q, the configuration

6

DYNAMIC PROGRAM FOR CAPACITATED VEHICLE ROUTING

15

specifies Iv,q and Ov,q which are respectively the number of tours that enter and exit Cb by vertex v
and that have visited exactly q clients at the moment they reach v. We refer to this as the flow in and
out of Cb at v. These values are sufficient to recover the intersection of the solution with the cluster:
connecting each entering tour with an exiting one, at minimal cost, gives the optimal solution.
To simplify the dynamic program, we first convert D into a nice tree decomposition with O(ωn) bags.
This can be done in polynomial time, while preserving the width [15]. In a nice tree decomposition,
each leaf bag contains a single vertex and each non-leaf bag of the decomposition is one of three types:
• An introduce bag b has one child b0 , such that b = b0 ∪{v} for some vertex v ∈
/ b0 . The vertex v
is introduced at b.
• A forget bag b has one child b0 , such that b = b0 \ {v} for some vertex v ∈ b0 . The vertex v is
forgotten at b.
• A join bag b has two children b1 and b2 such that b = b1 = b2 .
Moreover, as observed in [15], the third property of a tree decomposition ensures that each vertex
can be forgotten only once.
Furthermore, we assume the forget bag for the depot occurs at the root of the decomposition. If
not, s can be added to every bag in the tree, and the leaves extended. This results in a nice tree
decomposition with at most twice as many bags while adding at most one to the width.
A tour can be uncrossed to avoid crossing the same vertex in the same direction twice. As there are at
most n different tours, Iv,q ≤ n and Ov,q ≤ n, so there are nO(ωQ) possible configurations per bag. Since
there are O(ωn) bags in the nice tree decomposition, there are a total of nO(ωQ) different configurations.
The algorithm runs bottom-up: given a configuration for each child node, it finds all possible
compatible configurations for the parent node. Each different type of bag of the nice tree decomposition
requires a particular treatment.
For a leaf bag, b, containing vertex u, Cb is empty, so trivially there are no tours entering or exiting
Cb . For configurations with Iu,q = Ou,q = 0 for all q, the algorithm stores the cost zero.
For a forget bag, the parent bag b is equal to its child bag b0 minus some vertex u. For each child bag
configuration, the algorithm considers all ways to form a compatible parent bag configuration by rerouting u’s flow and, if u is a client, covering its demand, ρ(u). For each resulting parent bag configuration,
the dynamic program stores the cost only if it is less than the current value stored for that configuration.
After considering all child bag configurations and ways of forming a parent bag configuration, the values
stored in the table are guaranteed to be optimal. Consider some configuration for the child bag. First,
if u is a client, one tour is selected to visit it. There are three cases. If the tour crosses into Cb0 after
visiting u, the algorithm chooses a capacity q ≥ ρ(u) and makes the following changes to the flow at u:
Iu,q → Iu,q −1, Iu,q−ρ(u) → Iu,q−ρ(u) +1
There are at most Q such choices.
If the tour crosses out of Cb0 after visiting u, the algorithm chooses a capacity q ≤ Q − ρ(u) and
makes the following changes to the flow at u:
Ou,q → Ou,q −1, Ou,q+ρ(u) → Ou,q+ρ(u) +1
There are at most Q such choices.
Otherwise, the tour segment that visits u does not cross into Cb0 . The algorithm chooses v1 ,v2 ∈ b
and q ≤ Q−ρ(u), makes the following changes to the flow at v1 and v2 :
Iv1 ,q → Iv1 ,q +1, Ov2 ,q+ρ(u) → Ov2 ,q+ρ(u) +1,
and adds d(v1 ,u)+d(u,v2 ) to the intermediate configuration cost. There are ω 2 Q such choices. The
algorithm then reroutes all flow through u to some vertex in the parent bag, b. The algorithm chooses,
for each vertex v of b and each capacity, the number of the tours that enter (resp. exit) Cb0 though u
directly from (resp. to) v. Each such tour adds a cost of d(u,v) to the intermediate configuration cost.
There are O(n2ωQ ) such choices. Thus, for each child configuration there are O(ω 2 Qn2ωQ ) choices,
giving an nO(ωQ) overall runtime for each forget bag.

7

EMBEDDING FOR MULTIPLE DEPOTS

16

For an introduce bag, the parent bag is equal to its child bag plus some vertex u. Since the child
bag forms a boundary between the inside and outside of the cluster, no tour can cross directly into
the cluster via u, as it must first cross some vertex of the child bag. Therefore the only compatible
parent configurations are those that have no tours crossing at u. So for every parent configuration, if
Iu,q = Ou,q = 0 for all q, the algorithm stores the cost of the corresponding child configuration, namely
the configuration that results by removing u. Otherwise the cost is ∞.
For a join bag, the parent bag has two child bags identical to itself. Lemma 18 presents an oracle
that tells, in constant time, the minimal cost needed to form parent configuration (I 0 ,O0 ) given child
configurations (I 1 ,O1 ) and (I 2 ,O2 ), with an infinite cost if the configurations are not compatible. The
algorithm tries all combinations of configurations: the complexity of this step is nO(ωQ) .
Since each vertex will appear exactly once in a forget bag, each client will be visited exactly once.
The overall complexity is nO(ωQ) , as claimed. The algorithm considers all possible solutions and
outputs the minimal one, so the resulting cost is optimal.
Lemma 18. For each join bag b, it is possible to compute, in O(n6ωQ ) time, a table Tb such that
Tb [(I 0 ,O0 ),(I 1 ,O1 ),(I 2 ,O2 )] is the minimal cost to connect child configurations (I 1 ,O1 ) and (I 2 ,O2 )
to form parent configuration (I 0 ,O0 ) of b.
Proof. We design a dynamic program to compute this table. The base cases are when I 0 = I 1 +I 2 .
If O0 = O1 +O2 the cost is 0, since the configurations are therefore compatible. Otherwise the cost
is ∞, because it is not possible to balance incoming and outgoing flow.
1 +I 2 −I 0 = x 6= 0.
For the recursion step, assume I 0 6= I 1 +I 2 . Pick the first pair (u,q) such that Iu,q
u,q
u,q
If x < 0, the incoming flow at u with capacity q is bigger in b than in its child bags. Since this is not
possible, the cost is ∞. Otherwise, some flow entering Cluster 1 comes from Cluster 2 (or vice versa).
Suppose this flow exits Cluster 2 at vertex v: it means that
Tb [(I 0 ,O0 ),(I 1 ,O1 ),(I 2 ,O2 )] = Tb [(I 0 ,O0 ),(Iˆ1 ,O1 ),(I 2 ,Ô2 )]+d(u,v)
1
1
1 − 1} and Ô 2 = {O 2 ,O 2 − 1}. By this equation, the algorithm connects one
where Iˆ = {I ,Iu,q
v,q
segment exiting Cluster 2 at v with capacity q to a segment entering Cluster 1 at u. The value of
Tb [(I 0 ,O0 ),(I 1 ,O1 ),(I 2 ,O2 )] can therefore be computed in ω steps, by applying the above equality for
each vertex v of the boundary and storing the minimum value. This computation requires O(ωQ)
operations to find the pair (u,q), and then O(ω) operations to compute the value of the table. The
recursion step therefore requires O(ωQ) time.
As there are O(n6ωQ ) states for this DP, the overall complexity is therefore O(ωQn6ωQ ) = O(n6ωQ ),
concluding the proof.

7

Embedding for Multiple Depots

We present in this section how to extend Theorem 3 and apply it to several problems.

7.1

Theorem

Theorem 4 There is a function f (·,·,·) such that, for every ε > 0, graph G of highway dimension η
and set S of vertices of G, there exists a graph H and an embedding φ(·) of G into H such that
• H has treewidth f (η,|S|,ε), and
• for all vertices u and v,
dG (u,v) ≤ dH (φ(u),φ(v)) ≤ (1+O(ε))dG (u,v)+εmin(dG (S,u),dG (S,v))
We slightly modify the embedding of Theorem 3 in that purpose. We assume that the vertices of
S do not appear in non-trivial towns. This assumption is safe because, using S, we can apply the

7

EMBEDDING FOR MULTIPLE DEPOTS

17

modification of Lemma 5 to satisfy this assumption without asymptotically changing the diameter
or size of the graph. Note that the modification preserves all distances from the original input graph
but increases the highway dimension to η+|S|.
The algorithm computes the town decomposition with respect to the shortest-path covers, and
embeds the top-level towns using Lemma 6. By analogy with Section 4, we define the set X0i to be a
ε2i -net of ∪s∈S Bs (2i ) (and we ensure moreover that the X0i are nested). We also modify the definition
of l(X ): for a set X , l(X ) = dlog2 (maxv∈X d(S,v))e. Following Section 4, the host graph connects every
l(T )+log2 (1/ε)
l(T )
vertex v of a town T to every hub h in X0 ,...,X0
with an edge of length dG (v,h).
We now prove that this embedding has the properties of Theorem 4. We use H to denote the host
graph produced by the embedding. First, we prove the first point: the treewidth is bounded.
Proof. Let θS be the doubling dimension of the union of the approximate core hubs with S. The
shortest-path
covers are locally (η + |S|) log(η
+ |S|)-sparse [1], therefore Lemma 4 gives, θS =


2
O log (η + |S|) log(η + |S|)log(1/ε) + |S| , where the final |S| term comes from the extra balls
required to cover S. The proof of Lemma 13 directly gives that |X0i | ≤ |S|( 2ε )θS . Finally, following
the proof of Lemma 14, the host graph has a treewidth bounded by a function of η, |S| and ε.
We now prove the distortion bound.
Proof. Let u and v be two points of the metric space and h be the approximate core hub such that
dG (u,h)+dG (v,h) ≤ (1+O(ε))dG (u,v). Let su , sv and sh denote the points of S closest to u,v and h.
The proof is divided into three parts, according to the distances between l(h), l(Tu ) and l(Tv ).

(a) u and v are adjacent to ĥ

(b) only v is adjacent to ĥ

(c) u and v are not adjacent
to ĥ

Figure 5: The shortest path between u and v is approximated in the host graph by the dashed line.
In case (a), the distance from u and v to their centers is large compared to the distance between h
and sh ; in case (b), only the distance from v to sv is large, and in case (c) the distance from h to sh
is larger than the other two.
We first prove an inequality that is used several times:
dG (h,sh ) ≤ (1+O(ε))dG (u,v)+min(dG (u,su ),dG (v,sv ))
(1)
The definition of sh leads indeed to dG (h,sh ) ≤ dG (h,su ) and using the triangle inequality we obtain
dG (h,sh ) ≤ dG (h,u)+dG (u,su ). By definition, h is near the shortest path between u and v: this gives
the desired bound for u (the same holds for v).
Consider three cases, illustrated in Figure 5. Suppose that both l(h) ≤ l(Tu )+log2 (1/ε) and l(h) ≤
l(h)
l(Tv )+log2 (1/ε) (see Figure 5a). Let ĥ be the point in X0 closest to h: by definition of a net, dG (h,ĥ) ≤

7

EMBEDDING FOR MULTIPLE DEPOTS

18

ε2l(h) ≤ 2εdG (h,sh ); by construction of the embedding, ĥ is adjacent to u and v. In this case, we have
dH (u,v) ≤ dH (u,ĥ)+dH (ĥ,v) ≤ dG (u,ĥ)+dG (ĥ,v) ≤ dG (u,h)+dG (v,h)+2dG (h,ĥ)
We infer from the definition of h and ĥ that dH (u,v) ≤ (1 + O(ε))dG (u,v) + 4εdH (h,sh ) and using
Equation 1
dH (u,v) ≤ (1+O(ε))dG (u,v)+O(ε)min(dG (u,S),dG (v,S))
.
Then suppose that l(h) > l(Tu )+log2 (1/ε) but l(h) ≤ l(Tv )+log2 (1/ε) (see Figure 5b). It means that
u is not adjacent to ĥ but v is. It means in particular that dG (sh ,h) > 1ε dG (su ,u). The shortest-path
between u and v is therefore approximated in the host graph by the path u, su , ĥ, v. The edges along
this path have the length as in G, therefore dH (u,v) ≤ dH (u,su ) + dH (su , ĥ) + dH (ĥ,v) ≤ dG (u,su ) +
dG (su ,ĥ)+dG (ĥ,v). We now apply the triangle inequality in G: dG (su ,ĥ) ≤ dG (su ,u)+dG (u,ĥ). Using
the former inequality and previously-derived bounds gives
dH (u,v) ≤ 2dG (u,su )+dG (u,ĥ)+dG (ĥ,v) ≤ 2εdG (h,sh )+dG (u,h)+dG (h,v)+2dG (ĥ,h)
Recall that dG (h,ĥ) ≤ 2εdG (h,sh ) and dG (u,h)+dG (h,v) ≤ (1+ε)dG (u,v). Using this and Equation 1
finally gives
dH (u,v) ≤ (1+ε)dG (u,v)+4εdH (h,sh ) ≤ (1+O(ε))dG (u,v)+O(ε)min(dG (u,S),dG (v,S))
.
Finally, suppose that l(h) > l(Tu )+log2 (1/ε) and l(h) > l(Tv )+log2 (1/ε) (see Figure 5c). It means
in particular that neither u nor v is adjacent to ĥ. In this case, the shortest path between u and v
is approximated in the host graph by the path u,su ,ĥ,sv ,v: using the same arguments as in the former
case, we derive that dH (u,v) ≤ (1+O(ε))dG (u,v)+O(ε)min(dG (u,S),dG (v,S)).

7.2

Applications

Multiple-Depot Capacitated Vehicle Routing
The first application we consider is for Multiple-Depot Capacitated Vehicle Routing with
a constant number of depots. Let S denote the set of depots, and recall that Z is the set of clients.
We assume that any vertices added in the modification in Lemma 5 do not have any client demand.
Generalizing
the algorithm from Section 5 relies on generalizing the lower bound given in Lemma 1
P
to Q1 {d(c,S) : c ∈ Z}, as proved in [13]. This lower bound allows for an error of εd(c,S) for each
client c: the embedding of Theorem 4 can therefore be applied.
Theorem 5. For any  > 0, η > 0, k and any Q > 0, there is a polynomial-time algorithm that, given
an instance of Multiple-Depots Capacitated Vehicle Routing in which the capacity is Q, the
number of depots is k and the graph has highway dimension at most η, finds a solution whose cost is
at most 1+ times optimum.
The proof that an optimal solution in the host graph gives an approximate solution on the original
graph follows directly from Lemma 16, and the DP presented in Section 6 can be extended easily:
for a constant number of depots and a constant highway dimension, the embedding gives a constant
treewidth.

k-center
Another application is to get a fixed-parameter approximation (FPA) for k-center in a graph G
with highway dimension η, i.e. an algorithm with running time f (η,k)nO(1) .
The algorithm proceeds in two steps: first, computes a constant-factor approximation S (see [29]
or [22] for a 2-approximation). Applying Theorem 4 to G with the set S gives a host graph. Finally,
the algorithm runs a DP that gives a (1+ε)-approximation of the optimal solution in the host graph

REFERENCES

19

(where any vertices added in the modification in Lemma 5 are not required to be covered). We prove
that this solution is also a (1+ε)-approximation of the optimal solution in the original graph.
Lemma 19. A (1+ε)-approximation of k-center in the host graph given by Theorem 4 is a (1+O(ε))approximation of k-center in the original graph.
Proof. Let OPTH denote the optimal solution in the graph H. For each vertex u, let cu denote the
closest center to u in OPTG . We have the following:
costH (OPTG ) = max dH (u,cu ) ≤ max (1+O(ε))dG (u,cu )+O(ε)min(dG (u,S),dG (cu ,S))
u∈V (G)

u∈V (G)

This inequality can be rewritten
costH (OPTG ) ≤ (1+O(ε)) max dG (u,cu ) + O(ε) max dG (u,S)
u∈V (G)

u∈V (G)

Since the set S is a O(1)-approximate solution in G, costH (OPTG ) ≤ (1 + O(ε))costG (OPTG ) +
O(ε)costG (OPTG ) = (1+O(ε))costG (OPTG ). By definition of OPTH , costH (OPTH ) ≤ costH (OPTG )
and therefore costH (OPTH ) ≤ (1+O(ε))costG (OPTG ). That is, since the optimal solution in H is
an approximate solution in G, an approximate solution in H is also an approximate solution in G.
The complexity of finding a constant-factor approximation and of constructing the embedding is
a polynomial in n with fixed degree. The complexity of the DP given by Schild, Fox-Epstein and
Klein [20] for a treewidth tw is O(n(logn)tw ) which is O(nO(1) tw2tw ) following Lemma 1 in Katsikarelis
et al. [31]. As the treewidth only depends on the highway dimension η, k and , the FPA claims follows.

k-median
The last application presented here is to get a FPA k-median. The outline is the same as for k-center:
first compute a constant-factor approximation S (see [35]), then apply Theorem 4 using the set S and
finally compute an approximate solution in the host graph. The dynamic program for k-center can
be adapted to solve k-median with the same complexity (again, any vertices added in the modification
in Lemma 5 do not contribute to the cost). The following lemma is straightforward:
Lemma 20. A (1+ε)-approximation of k-median in the host graph given by Theorem 4 is a (1+O(ε))approximation of k-median in the original graph.
The proof is indeed the same as for Lemma 19, replacing the max by a sum.
Theorem 2 There is a function f (·,·,·) and a constant c such that, for each of the problems k-Center
and k-Median, for any η > 0,k > 0 and ε > 0, there is an f (η,k,ε)nc algorithm that, given an instance
in which the graph has highway dimension at most η, finds a solution whose cost is at most 1+ε times
optimum.

Acknowledgements
Thanks to Andreas Feldmann and Vincent Cohen-Addad for helpful discussions and comments.

References
[1] I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck. Vc-dimension and shortest
path algorithms. In International Colloquium on Automata, Languages, and Programming,
pages 690–699. Springer, 2011.
[2] I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension and
provably efficient shortest path algorithms. J. ACM, 63(5):41:1–41:26, Dec. 2016.

REFERENCES

20

[3] I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension, shortest paths, and
provably efficient algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 782–793. Society for Industrial and Applied Mathematics, 2010.
[4] A. Adamaszek, A. Czumaj, and A. Lingas. PTAS for k-tour cover problem on the plane for
moderately large values of k. Algorithms and Computation, pages 994–1003, 2009.
[5] S. Arora, P. Raghavan, and S. Rao. Approximation schemes for Euclidean k -medians and related
problems. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing,
Dallas, Texas, USA, May 23-26, 1998, pages 106–113, 1998.
[6] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics
for k-median and facility location problems. SIAM Journal on Computing, 33(3):544–562, 2004.
[7] T. Asano, N. Katoh, and K. Kawashima. A new approximation algorithm for the capacitated
vehicle routing problem on a tree. Journal of Combinatorial Optimization, 5(2):213–231, 2001.
[8] T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama. Covering points in the plane by k-tours: a
polynomial approximation scheme for fixed k. IBM Tokyo Research Laboratory Research Report
RT0162, 1996.
[9] T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama. Covering points in the plane by k-tours:
towards a polynomial time approximation scheme for general k. In Proceedings of the
Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 275–283. ACM, 1997.
[10] M. Bădoiu, S. Har-Peled, and P. Indyk. Approximate clustering via core-sets. In STOC, pages
250–257, 2002.
[11] H. Bast, S. Funke, and D. Matijevic. Ultrafast shortest-path queries via transit nodes. In The
Shortest Path Problem, pages 175–192, 2006.
[12] H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. In transit to constant time
shortest-path queries in road networks. In Proceedings of the Meeting on Algorithm Engineering
& Expermiments, pages 46–59. Society for Industrial and Applied Mathematics, 2007.
[13] A. Becker, K. Philip N., and D. Saulpic. A quasi-polynomial-time approximation scheme for
vehicle routing on planar and bounded-genus graphs. In European Symposium on Algorithms.
Springer, 2017. to appear.
[14] V. Cohen-Addad, P. N. Klein, and C. Mathieu. Local search yields approximation schemes for
k-means and k-median in Euclidean and minor-free metrics. In 57th Annual IEEE Symposium
on Foundations of Computer Science FOCS, pages 353–364, 2016.
[15] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and
S. Saurabh. Parameterized algorithms, volume 3, chapter 7: Treewidth. Springer, 2015.
[16] A. Das and C. Mathieu. A quasipolynomial time approximation scheme for euclidean capacitated
vehicle routing. Algorithmica, 73(1):115–142, 2015.
[17] T. Feder and D. Greene. Optimal algorithms for approximate clustering. In Proceedings of the
twentieth annual ACM symposium on Theory of computing, STOC ’88, pages 434–444, New
York, NY, USA, 1988. ACM.
[18] A. E. Feldmann. Fixed parameter approximations for k-center problems in low highway
dimension graphs. In Proceedings, Part II, of the 42nd International Colloquium on Automata,
Languages, and Programming, pages 588–600. Springer-Verlag New York, Inc., 2015.

REFERENCES

21

[19] A. E. Feldmann, W. S. Fung, J. Könemann, and I. Post. A (1+ε)-embedding of low highway
dimension graphs into bounded treewidth graphs. In International Colloquium on Automata,
Languages, and Programming, pages 469–480. Springer, 2015.
[20] E. Fox-Epstein, P. N. Klein, and A. Schild. Embedding planar graphs into low-treewidth graphs,
with application to efficient approximation schems for metric problems. Unpublished manuscript,
2017.
[21] B. L. Golden and R. T. Wong. Capacitated arc routing problems. Networks, 11(3):305–315, 1981.
[22] T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical
Computer Science, 38:293–306, 1985.
[23] S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. Journal
of Algorithms, 31(1):228–248, 1999.
[24] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion
embeddings. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE
Symposium on, pages 534–543. IEEE, 2003.
[25] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion
embeddings. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer
Science, pages 534–543. IEEE, 2003.
[26] V. Guruswami and P. Indyk. Embeddings and non-approximability of geometric problems. In
SODA, volume 3, pages 537–538, 2003.
[27] M. Haimovich and A. Rinnooy Kan. Bounds and heuristics for capacitated routing problems.
Mathematics of operations Research, 10(4):527–542, 1985.
[28] S. Hamaguchi and N. Katoh. A capacitated vehicle routing problem on a tree. In International
Symposium on Algorithms and Computation, pages 399–407. Springer, 1998.
[29] D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem.
Mathematics of Operations Research, 10(2):180–184, 1985.
[30] K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median
problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM (JACM),
48(2):274–296, 2001.
[31] I. Katsikarelis, M. Lampis, and V. T. Paschos. Structural parameters, tight bounds, and
approximation for (k,r)-center. arXiv preprint arXiv:1704.08868, 2017.
[32] M. Khachay and R. Dubinin. PTAS for the euclidean capacitated vehicle routing problem in
Rd . In Proceedings of the 9th International Conference on Discrete Optimization and Operations
Research (DOOR 2016), pages 193–205. Springer, 2016.
[33] S. Li and O. Svensson. Approximating k-median via pseudo-approximation. SIAM Journal
on Computing, 45(2):530–547, 2016.
[34] J. Plesnı́k. On the computational complexity of centers located in a graph. Aplikace matematiky,
25(6):445–452, 1980.
[35] D. B. Shmoys, É. Tardos, and K. Aardal. Approximation algorithms for facility location
problems. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing,
pages 265–274. ACM, 1997.

A

A

DEFINITIONS OF HIGHWAY DIMENSION

22

Definitions of highway dimension

The definition of highway dimension we use is the one given by Feldmann et al. [19]. However, alternate
definitions exist. We summarize here the differences between them that are discussed in Feldmann et al.
The original definition comes from Abraham et al. [3], in 2010. Their work uses c = 4, but interestingly
they remark that “one could use constants bigger than 4”. Nonetheless, Feldmann et al. [19] shows
that changing the constant is not innocuous: for any constant c, there is a graph with n vertices that
has highway dimension 1 with respect to c and highway dimension Ω(n) with respect to any c0 > c.
Another definition of highway dimension comes from a 2011 paper of Abraham et al. [1]. Their
definition differs from Definition 1 in that they use c = 2 and all shortest paths of length in (r,2r]
that intersect the ball Bv (2r) (not just the ones that stay inside the ball). This is a generalization
of Definition 1 for c = 4: a path of length at most 2r that intersects the ball Bv (2r) is also entirely
contained in the ball Bv (4r). As is, the results of Feldmann et al. and, consequently, the ones presented
in this paper cannot be generalized to this definition.
The last noteworthy definition of highway dimension was also introduced by Abraham et al. [2] in a
journal paper in 2016 (we use h to denote this parameter, different from η). This definition is stricter
than the one of 2010 (and therefore the one of our paper), Feldmann et al. show that if a metric has
a highway dimension h according to the 2016 definition, it has a highway dimension O(h2 ) according
to the 2010 definition.

B

Proof Sketches of Section 2 Lemmas

We now give proof sketches for Lemma 2 and Lemma 3, restated here for convenience. See [19] for
full proofs.
Lemma. 2.[Lemma 3.2 in [19]]
If T is a town at scale r, then
1. diam(T ) ≤ r and
2. d(T,V \T ) > r
Proof. We give a sketch of the proof from [19]. For the first point (illustrated on Figure 6a), let u and v
be two vertices of the same town. It means that there exists w such that d(u,w) ≤ r and d(v,w) ≤ r (by
definition of a town). So d(u,v) ≤ 2r. Suppose by contradiction that d(u,v) > r : it means that d(u,v) ∈
(r,2r] ⊆ (r,cr/2] (because c > 4). Therefore there exists a point of the shortest-path cover for scale r on the
path between u and v: this point is at a distance at most r from u or v (because d(u,v) ≤ 2r), and therefore
2r from w, which contradicts the construction of the town. Therefore d(u,v) ≤ r, and diam(T ) ≤ r.
We proceed similarly for the second point, illustrated in Figure 6b. Let u ∈ T,v ∈ V \T , and suppose
by contradiction that d(u,v) ≤ r. The definition of T gives a point w such that d(u,w) ≤ r, d(v,w) > r
and d(w,SP C(r)) > 2r. Combining the inequalities gives that r < d(v,w) ≤ d(u,v)+d(u,w) < 2r < cr/2.
By definition of the shortest-path cover, there is a hub h on the shortest path between v and w, so
d(w,h) ≤ d(w,v) ≤ 2r, which contradicts the choice of w. That concludes the proof.
Lemma. 3.[Lemma 3.3 in [19]]
For every town T in a town decomposition T ,
1. T has either 0 children or at least 2 children, and
2. if T is a town at level i and has child town T 0 at level j, then j < i.
Proof. We sketch the proof from [19]. The first property comes from the facts that every singleton is a
town at level 0 and that if T 0 is a child town of T , then T \T 0 =
6 ∅. The second property is a consequence
of the first one combined with the isolation of the child town T 0 .

C

PROOF OF LEMMA ??

(a) First
d(u,v) ≤ r

23

contradiction:

(b) Second contradiction :
d(T,V \T ) > r

Figure 6: The shortest path cover is represented with black dots, the other points are grey dots. The
dashed circles are towns.

C

Proof of Lemma 5

In Section 2 we emphasize that the shortest-path covers are required to be inclusion-wise minimal, and
that we cannot simply add the depot to the shortest-path cover at every scale. In fact, doing so actually
is safe. This is not immediately obvious, as this modification can greatly alter the town decomposition.
However, the only risk in adding a hub to the shortest-path cover is exceeding the bound on the doubling
dimension of XT for some town T . Indeed, the only place where Feldmann et al. [19] depend on the
shortest-path covers being inclusion-wise minimal is in the proof of this doubling-dimension bound.
It is fairly simple to adapt their proofs to show that adding a fixed number of vertices to a minimal
shortest-path cover at every levels adds at most a small factor to the bound on the doubling dimension.
Instead of reproving their results, however, we modify the graph to give the desired property. We
now prove the claimed properties of the Lemma 5 modification (restated for convenience).
Lemma. 5. Any graph G = (V,E) with highway dimension η, diameter ∆G , and designated vertex set
S ⊆ V can be modified by adding O(η 2 |S|3 log∆G ) new vertices and edges, such that the resulting graph
G0 = (V 0 ,E 0 )
• has highway dimension at most η+|S|
• for all u,v,∈ V 0 , dG0 (u,v) ∈ ( 2c ,

3c
4 ∆G ]

• for all u,v ∈ V , dG0 (u,v) = dG (u,v), and
• for every s ∈ S, the only towns containing s in the town decomposition of G0 are the trivial towns.
Proof. Let a ∈ Z be the smallest integer such that ( 4c )a > 2c and let b ∈ Z be the smallest integer
such that ( 4c )b > ∆G . We modify G by adding, for each i ∈ {a, a+1,..., b} and each s ∈ S, (η +|S|)2
copies of vertex vis and an edge (s,vis ) of length ri = ( 4c )i for each copy. This modification adds
(η+|S|)2 |S|(b−a+1) = O(η 2 |S|3 log∆G ) vertices and edges (see Figure 7). We show that each of the
listed properties holds for the modified graph G0 .
First, this modification increases the highway dimension by at most |S|, since adding S as hubs
covers all newly introduced shortest paths.
Second the smallest introduced edge has length ( 4c )a > 2c , and all point-to-point distances in G
are already assumed to be greater than 2c (see Section 2). The largest introduced edge has length

C

PROOF OF LEMMA ??

24

( 4c )b > ∆G ≥ ( 4c )b−1 , so the largest point-to-point distance in G0 is between two copies of vbs from distinct
c b−1
vertices s1 ,s2 ∈ S, namely ∆G0 ≤ 2( 4c )b +∆G < 3( 4c )b = 3c
≤ 3c
4 (4)
4 ∆G .
Third, all newly added edges are only connected to vertices in S, so all point-to-point distances
between vertices in V are preserved in G0 .
Finally, recall that the trivial towns in the town decomposition of G0 are the singleton towns at
scale r0 = ( 4c )0 = 1 and the topmost town at scale rmax = dlogc/4 diam(G0 )e that contains all of G0 .
By the second property above, all point-to-point distances in G0 are greater than c/2 and, clearly, at
most diam(G0 ). Therefore there are no shortest paths in G0 in the intervals (1,c/2] or (rmax , 2c rmax ],
so SP C(r0 ) = SP C(rmax ) = ∅. So all of G0 is in the trivial town at scale rmax and each vertex v ∈ V 0 ,
including each s ∈ S, is in a trivial singleton town at scale r0 . Consider some s ∈ S. We must show
that s does not appear in a town at any scale ri ∈ [r1 ,rmax ).
We first show that for every scale ri = ( 4c )i ∈ [ 4c , ( 4c )b ) = [r1 , rb ), every locally-sparse shortestpath cover SPC ( 4c )i of G0 includes
s, and therefore s cannot be in any town at these scales. The

shortest path cover SPC ( 4c )i must
contain a hub on each path with length in (( 4c )i , 2c ( 4c )i ]. By

the first property above, SPC ( 4c )i is guaranteed to be locally (η + |S|)log(η + |S|)-sparse [1], so
Bs (c( 4c )i )∩SPC(( 4c )i ) ≤ (η+|S|)log(η+|S|) < (η+|S|)2 . There are two cases to consider.
If 4c ≤ ( 4c )i < ( 4c )a , then ( 4c )a ∈ (( 4c )i , 2c (4c )i ], since ( 4c )a−1 ≤ 2c implies ( 4c )a ≤ 2c ( 4c ) ≤ 2c ( 4c )i . Since each
edge (s,vas ) has length ( 4c )a , SPC (4c )i must contain either s or all (η + |S|)2 copies of vas . By the
sparsity argument above, SPC ( 4c )i must therefore contain s.
Otherwise, ( 4c )a ≤ ( 4c )i < ( 4c )b . Therefore, ( 4c )i+1 ≤ ( 4c )b , so there are (η +|S|)2 newly added edges
s ) of length ( c )i+1 . Furthermore ( c )i+1 ∈ (( c )i , c ( c )i ], since c < c . Therefore SPC ( c )i must
(s,vi+1
4
4
4
2 4
4
2
4

s . Again, by the sparsity argument above, SPC ( c )i
contain either s or all (η +|S|)2 copies of vi+1
4
must therefore contain s.
What remains to show is that s is in no town at scales in [rb ,rmax ). We show that in fact there
are no non-trivial towns at these levels. Assume to the contrary that T is a non-trivial town at scale
ri ∈ [rb ,rmax ). By Lemma 2, dG0 (T,V 0 \T ) > ri . In particular, any edges in the cut δ(T ) must have
length greater than ri . Furthermore since T is non-trivial, T 6= V 0 , and since G0 is connected, δ(T ) 6= ∅.
Therefore there is some edge in G0 that has length greater than ri and thus greater than rb . However
all edges from G have length at most ∆G < rb , and all newly added edges have length at most rb .
Therefore no such town exists.

C

PROOF OF LEMMA ??

25

Figure 7: Here, S = {s1 ,s2 ,s3 } is depicted as hollow vertices in G. For each s ∈ S, the modification
of G to G0 introduces new vertices and edges between these new vertices and s.

