arXiv:1708.04215v2 [cs.DS] 6 Nov 2017

A Constant-Factor Approximation Algorithm for the
Asymmetric Traveling Salesman Problem*
Ola Svensson†

Jakub Tarnawski†

László A. Végh‡

November 7, 2017

Abstract
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to
the standard LP relaxation, and thus our result confirms the conjectured constant
integrality gap of that relaxation.
Our techniques build upon the constant-factor approximation algorithm for
the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those
arising from node-weighted metrics. For those instances, we then solve LocalConnectivity ATSP, a problem known to be equivalent (in terms of constant-factor
approximation) to the asymmetric traveling salesman problem.
Keywords: approximation algorithms, asymmetric traveling salesman problem, combinatorial
optimization, linear programming

* This is the full version of the paper. There is also a 10-page extended abstract available from the
authors’ homepages, which gives an overview of the main ideas and techniques.
†
École Polytechnique Fédérale de Lausanne. Email: firstname.lastname@epfl.ch. Supported by ERC
Starting Grant 335288-OptApprox.
‡
London School of Economics. Email: l.vegh@lse.ac.uk. Supported by EPSRC First Grant
EP/M02797X/1.

1 Introduction
The traveling salesman problem — to find the shortest tour visiting n given cities — is
one of the best-known NP-hard optimization problems.
Without any assumptions on the distances, a simple reduction from the problem
of deciding whether a graph is Hamiltonian shows that it is NP-hard to approximate
the shortest tour to within any factor. Therefore it is common to relax the problem by
allowing the tour to visit cities more than once. This is equivalent to assuming that the
distances satisfy the triangle inequality: the distance from city i to k is no larger than
the distance from i to j plus the distance from j to k. All results mentioned and proved
in this paper refer to this setting.
If we further assume the distances to be symmetric, then Christofides’ classic
algorithm from 1976 [Chr76] is guaranteed to find a tour of length at most 3/2 times the
optimum. Improving this approximation guarantee is a notorious open question in
approximation algorithms. There has been a flurry of recent progress in the special case
when distances are given as unweighted shortest path metrics [GSS11, MS16, Muc12,
SV14]. However, even though the standard linear programming (LP) relaxation is
conjectured to approximate the optimum within a factor of 4/3, it remains an elusive
problem to improve upon Christofides’ algorithm.
If we do not restrict ourselves to symmetric distances, we obtain the more general
asymmetric traveling salesman problem (ATSP). Compared to the symmetric setting,
the gap in our understanding is much larger, and the current algorithmic techniques
have failed to give any constant approximation guarantee. This is intriguing especially
since the standard LP relaxation, also known as the Held-Karp lower bound, is conjectured to approximate the optimum to within a small constant. In fact, it is only known
that its integrality gap1 is at least 2 [CGK06].
The first approximation algorithm for ATSP was given by Frieze, Galbiati and
Maffioli [FGM82], achieving an approximation guarantee of log2 (n). Their elegant “repeated cycle cover” approach was refined in several papers [Blä08, KLSS05, FS07], but
there was no asymptotic improvement in the approximation guarantee until the more recent O(log n / log log n)-approximation algorithm by Asadpour et al. [AGM+ 10]. They
introduced a new and influential approach to ATSP based on a connection to the
graph-theoretic concept of thin spanning trees. This has further led to improved algorithms for special cases of ATSP, such as graphs of bounded genus [GS11]. Moreover,
Anari and Oveis Gharan recently exploited this connection to significantly improve
the best known upper bound on the integrality gap of the standard LP relaxation
to O(poly log log n) [AG15]. This implies an efficient algorithm for estimating the
optimal value of a tour within a factor O(poly log log n) but, as their arguments are
non-constructive, no approximation algorithm for finding a tour of matching guarantee.
Around the same time, an alternative approach was introduced by Svensson [Sve15]. It reduces the task of approximating ATSP to a seemingly easier problem
called Local-Connectivity ATSP. The paper [Sve15] also gave an algorithm for Local1

Recall that the integrality gap is defined as the maximum ratio between the optimum values of the
exact (integer) formulation and of its relaxation.

2

Connectivity ATSP restricted to the special case of node-weighted metrics, implying
a constant-factor approximation algorithm for that special case. We have generalized
this to graphs with at most two different edge weights in subsequent work [STV16]. In
this paper, we build upon and generalize both of these results to give a constant-factor
approximation algorithm for all metrics.
Theorem 1.1. There is a polynomial-time algorithm for ATSP that returns a tour of value at
most a constant times the Held-Karp lower bound.
We remark that we have not optimized the constant of the approximation guarantee, instead favoring simplicity. However, we believe that further developments
are needed to get close to the lower bound of 2 on the integrality gap [CGK06] and
the inapproximability of 75/74 [KLS13]. See the conclusions (Section 9) for further
discussion and open problems.
Brief overview of approach and outline of paper. The paper [Sve15] has introduced
the problem Local-Connectivity ATSP and showed that it is equivalent (in terms of
constant-factor approximation) to the asymmetric traveling salesman problem. Further, it gave an efficient solution to Local-Connectivity ATSP for node-weighted graphs.
In [STV16] we gave a solution for graphs with two different edge weights. This, however, turned out to be technically challenging. In fact, it is unclear if the same approach
can be extended even to a fixed number of different edge weights.
In the current paper we take a different route. Instead of trying to directly tackle
Local-Connectivity ATSP in arbitrary weighted graphs, the first part of our argument uses a sequence of natural reductions to reduce the problem of approximating
ATSP in general to that of approximating ATSP on special, structured instances called
vertebrate pairs. These instances enjoy properties that make them amenable for LocalConnectivity ATSP.
The reduction to structured instances is itself done in several steps that we now
briefly explain. It will be convenient to define ATSP in terms of its graphic formulation:
Definition 1.2. The input for ATSP is a pair (G, w), where G is a strongly connected
directed graph (digraph) and w is a nonnegative weight function defined on the edges.
The objective is to find a closed walk of minimum weight that visits every vertex at
least once.
Without loss of generality, one could assume that G is a complete digraph. However,
for our reductions, it will be important that G may not be complete. We also remark
that a closed walk that visits every vertex at least once is equivalent to an Eulerian
multiset of edges that connects the graph. (An edge set of a digraph is Eulerian if the
in-degree of each vertex equals its out-degree.)
In the preliminaries (Section 2.2) we exploit the extreme point structure of the
LP relaxation and of its dual to show that we can focus on laminarly-weighted ATSP
instances: there is a laminar family L of vertex sets and a non-negative vector (yS )S∈L
P
such that any edge e has w(e) = S∈L:e∈δ(S) yS , where δ(S) denotes the edges in the cut
defined by S. See the left part of Figure 1 for an example. This is a generalization of

3

node-weighted metrics, which correspond to the case when the laminar family only
contains singleton sets.
We further explore the structure of sets in L: in Section 3 we study paths inside sets
S ∈ L and, in Section 4, we introduce analogs of the classic graph-theoretic operations
of contracting and inducing on such a set. These operations naturally give rise to
a recursive algorithm that, intuitively, works as long as the contraction of some set
S ∈ L results in a significant decrease in the value of the LP relaxation. In Section 5 we
formally analyze this recursive algorithm and reduce the task of approximating ATSP
to that of approximating irreducible instances: those where no set S ∈ L brings about a
significant decrease of the LP value if contracted.
Informally, every set S ∈ L in an irreducible instance has two vertices u, v ∈ S
such that the shortest path from u to v crosses a large (weighted) fraction of the
sets R ∈ L : R ( S (otherwise contracting S into a single vertex, endowed with a
node-weight equal to the weight of the shortest path, would lead to a decrease in
the LP value). This insight, together with the approximation algorithm for nodeweighted metrics in [Sve15], allows us to construct a low-weight subtour B that does
not necessarily visit every vertex but crosses every non-singleton set of L. See the
right part of Figure 1 for an example. We refer to B as a backbone, and to the ATSP
instance and the backbone together as a vertebrate pair. This reduction allows us to
further assume that our input is such a vertebrate pair; it is presented in Section 6.
In each of the above stages, we prove a theorem of the form: if there is a constantfactor approximation for ATSP on more structured instances, then there is a constantfactor approximation for ATSP on less structured instances. For instance, an algorithm
for irreducible instances implies an algorithm for laminarly-weighted instances. One
can also think of making a stronger and stronger assumption on the instance without
loss of generality, making it increasingly resemble a node-weighted metric.
Having reduced the original problem to vertebrate pairs, in Section 7 we give
an algorithm for Local-Connectivity ATSP for such instances. The main technical
ingredient of the argument is Lemma 7.3, where we use the idea of finding a minimumweight circulation in an auxiliary “split graph”. This is inspired by the paper [STV16]
on ATSP with two edge-weights, although the concepts are not identical, and (perhaps
surprisingly) the proof for general metrics is simpler. By our reductions and the result
in [Sve15] this then implies the main result, Theorem 1.1, as explained in Section 8.

2 Preliminaries
We let R+ denote the set of nonnegative real numbers. The support of a function
f : X →
P R+ is the subset {x ∈ X : f (x) > 0}. For a subset Y ⊆ X, we also use
f (Y) = x∈Y f (x).
For a digraph G, we let V(G) and E(G) denote the set of vertices and edges, respectively. We simply use V and E whenever the graph is clear from the context. By
an edge set F ⊆ E, we always mean an edge multiset: the same edge can be present
in multiple copies. We will refer to the union of two edge (multi)sets as a multiset
(adding up the multiplicities of every edge).
A closed walk is a subtour, and it is a tour if it visits every vertex at least once. As
4

e

Figure 1: On the left we give an example of a laminarly-weighted ATSP instance. The
sets of the laminar family are shown in gray. We depict a single edge e
that crosses three sets in the laminar family, say S1 , S2 , S3 , and so w(e) =
yS1 + yS2 + yS3 . On the right, we give an example of a vertebrate pair. Notice
that the backbone (depicted as the cycle) crosses all non-singleton sets of the
laminar family, though it may not visit all the vertices.
mentioned in the introduction, a tour is equivalent to an Eulerian multiset of edges
that connects the graph. Similarly, a subtour is equivalent to an Eulerian multiset of
edges that form a single component. In the sequel we use this viewpoint.
For a vertex set U ( V, we let G[U] denote the subgraph induced by U. That is,
G[U] is the subgraph of G whose vertex set is U and whose edge set consists of all
edges in E(G) with both endpoints in U. We also let G/U denote the graph obtained by
contracting the vertex set U, i.e., by replacing the vertices in U by a single new vertex
u and redirecting every edge with one endpoint in U to the new vertex u. This may
create parallel edges in G/U. We keep all parallel copies; thus, every edge in G/U will
have a unique preimage in G.
For vertex sets S, T ⊆ V we let δ(S, T) = {(u, v) ∈ E : u ∈ S \ T, v ∈ T \ S}. For
a set S ⊆ V we let δ+ (S) = δ(S, V \ S) denote the set of outgoing edges, and we let
δ− (S) = δ(V \ S, S) denote the set of incoming edges. Further, let δ(S) = δ− (S) ∪ δ+ (S).
For a vertex v ∈ V we let δ+ (v) = δ+ ({v}) and δ− (v) = δ− ({v}). For an edge (multi)set
F ⊆ E, we use δF (S, T) = δ(S, T) ∩ F, δ+F (S) = δ+ (S) ∩ F, etc. Further, let 1F denote the
indicator vector of F, which has a coordinate for each edge e with value equal to the
multiplicity of e in F.
For a set S ( V we let Sin and Sout be those vertices of S that have an incoming edge
from outside of S and those that have an outgoing edge to outside of S, respectively.
That is,
Sin = {v ∈ S : δ− (S) ∩ δ− (v) , ∅},

and

Sout = {v ∈ S : δ+ (S) ∩ δ+ (v) , ∅} .

2.1 Held-Karp Relaxation
Given an edge-weighted digraph (G, w), the Held-Karp relaxation has a variable x(e) >
0 for every edge e ∈ E. The intended solution is that x(e) should equal the number of
times e is used in the solution. The linear programming relaxation LP(G, w) is now

5

defined as follows:
X

minimize

w(e)x(e)

e∈E

x(δ+ (v)) = x(δ− (v))
for v ∈ V,
x(δ(S)) > 2
for ∅ , S ( V,
x > 0.

subject to

(LP(G, w))

The optimum value of this LP is called the Held-Karp lower bound. The first set of
constraints says that the in-degree should equal the out-degree for each vertex, i.e., the
solution should be Eulerian. We call a vector x satisfying these constraints an Eulerian
vector. The second set of constraints enforces that the solution is connected. These
are sometimes referred to as subtour elimination constraints. Notice that the Eulerian
property implies x(δ− (S)) = x(δ+ (S)) for every set S ⊆ V, and therefore these constraints
are equivalent to x(δ+ (S)) > 1 for all ∅ , S ( V, which appear more frequently in the
literature. We use the above formulation as it enables some simplifications in the
presentation.
We say that a set S ⊆ V is tight with respect to a solution x to LP(G, w) if x(δ(S)) = 2,
that is, x(δ− (S)) = x(δ+ (S)) = 1.
Let us now formulate the dual linear program DUAL(G, w). We associate variables (αv )v∈V and (yS )∅,S⊂V with the first and second set of constraints of LP(G, w),
respectively.
maximize

X

2 · yS

∅,S(V

subject to

X

yS + αu − αv 6 w(u, v)

for (u, v) ∈ E,

(DUAL(G, w))

S:(u,v)∈δ(S)

y > 0.
For singleton sets {u}, we will also use the notation yu = y{u} . We remark that
although the Held-Karp relaxation has exponentially many constraints, it is wellknown that we can solve it in polynomial time either using the ellipsoid method with
a separation oracle, or by formulating an equivalent compact (polynomial-size) linear
program.
An optimal solution to DUAL(G, w) can also be found in polynomial time. To
see this, note that when solving LP(G, w), the ellipsoid method returns a polynomial
number of constraints used as cutting planes. These provide a polynomial-size family
S ⊆ 2V such that DUAL(G, w) has an optimal solution with support contained in S.
Moreover, we show that one can efficiently obtain a dual optimal solution with a “nice”
support, as stated below. Recall that a family L ⊆ 2V of vertex subsets is laminar if for
any A, B ∈ L we have either A ⊆ B or B ⊆ A or A ∩ B = ∅.
Lemma 2.1. For every edge-weighted digraph (G, w) there exists an optimal solution (α, y) to
DUAL(G, w) such that the support of y is a laminar family of vertex subsets. Moreover, such
a solution can be computed in polynomial time.
6

Proof. We start by showing the existence of a laminar optimal solution using a standard
uncrossing argument (see e.g. [CFN85] for an early application of this technique to
the Held-Karp relaxation of the symmetric traveling salesman problem). Select (α, y)
P
to be an optimal solution to DUAL(G, w) minimizing
S |S|yS . That is, among all
P
dual
solutions
that
maximize
the
dual
objective
2
y
,
we
select one that minimizes
S S
P
S |S|yS . We claim that the support L = {S : yS > 0} is a laminar family. Suppose not,
i.e., that there are sets A, B ∈ L such that A ∩ B, A \ B, B \ A , ∅. Then we can obtain a
new dual solution (α, ŷ), where ŷ is defined, for ε = min(yA , yB ) > 0, as


yS − ε




ŷS = 
yS + ε



y
S

if S = A or S = B,
if S = A \ B or S = B \ A,
otherwise.

That (α, ŷ) remains a feasible solution follows since ŷ remains non-negative (by the
selection of ε) and since for any edge e we have

1e∈δ(A) + 1e∈δ(B) > 1e∈δ(A\B) + 1e∈δ(B\A) .
P
P
Therefore S:e∈δ(S) ŷS 6 S:e∈δ(S) yS and so the constraint corresponding to edge e reP
P
mains satisfied. Further, we clearly have 2 S ŷS = 2 S yS . In other words, (α, ŷ) is an
optimal dual solution. However,
X
|S|(yS − ŷS ) = (|A| + |B| − |A \ B| − |B \ A|)ε > 0 ,
S

which
contradicts that (α, y) was selected to be an optimal dual solution minimizing
P
S |S|yS . Therefore, there can be no such sets A and B in L, and so it is a laminar family.
To find a laminar optimal solution in polynomial time, we start with an arbitrary
dual optimal solution. As noted above, one can be computed in polynomial time. Now
we apply the above uncrossing operation to obtain a laminar optimal solution. A result
by Karzanov [Kar96, Theorem 2] shows that if we carefully select the sequence of pairs
A, B to uncross, this can be performed in polynomial time (although for an arbitrary
sequence, the number of uncrossing steps may not be polynomially bounded).


2.2 Node-Weighted and Laminarly-Weighted ATSP
In [Sve15] a polynomial-time constant-factor approximation algorithm was given for
node-weighted ATSP. A weighted digraph (G, w) is called node-weighted if there exists a
function h : V → R+ such that w(u, v) = h(u) + h(v) for every (u, v) ∈ E.2 The main
result of [Sve15] is the following:
Theorem 2.2. For every ε > 0 there is a polynomial-time algorithm that, for any node-weighted
digraph (G, w), returns a tour of weight at most (27 + ε) times the optimum value of LP(G, w).
2

In [Sve15], the definition is slightly different: w(u, v) = f (u) for every (u, v) ∈ E for a function
f : V → R+ . The two definitions are equivalent: by assigning f (u) = 2h(u), the weight of any tour is
equal for the weights w(u, v) = f (u) and for the weights w(u, v) = h(u) + h(v).

7

We use αNW = 27 + ε to refer to the approximation guarantee of this algorithm in
order to exhibit the dependence of our results on this bound.
We now introduce a more complex class of cost functions, which takes solutions to
LP(G, w) and DUAL(G, w) into account.
Definition 2.3. A tuple I = (G, L, x, y) is called a laminarly-weighted ATSP instance if G
is a strongly connected digraph, L is a laminar family of vertex subsets, x is a feasible
solution to LP(G, 0), and y : L → R+ . We further require that xe > 0 for every e ∈ E
and that every set S ∈ L be tight with respect to x, i.e., that x(δ+ (S)) = x(δ− (S)) = 1. We
define the induced weight function wI : E → R+ as
X
yS
for every e ∈ E.
wI (e) =
S∈L: e∈δ(S)

Given an instance I as in the definition, the vectors x and y have the following
important property. Define a dual solution (ᾱ, ȳ) by setting ᾱu = 0 for all u ∈ V, and
ȳS = yS if S ∈ L and ȳS = 0 otherwise. Then complementary slackness implies that for
the induced weight function wI , the vector x is an optimal solution to LP(G, wI ) and
(ᾱ, ȳ) is an optimal solution to DUAL(G, wI ).
Our first main insight is that ATSP with arbitrary weights can be reduced to the
laminarly-weighted ATSP problem.
Theorem 2.4. Assume we have a polynomial-time algorithm that finds a solution of weight at
most α times the Held-Karp lower bound for every laminarly-weighted ATSP instance. Then
there is a polynomial-time algorithm for the general ATSP problem that finds a solution of
weight at most α times the Held-Karp lower bound.
Proof. Consider an arbitrary edge-weighted strongly connected digraph (G, w). Let x
be an optimal solution to LP(G, w) and let (α, y) be an optimal solution to DUAL(G, w)
as guaranteed by Lemma 2.1, that is, y has a laminar support L. We now define a pair
(G′ , w′ ) as
V(G′ ) = V(G) ,

E(G′ ) = {e ∈ E(G) : x(e) > 0} ,

and

w′ (u, v) = w(u, v) − αu + αv .

We claim that I = (G′ , L, x, y) is a laminarly-weighted ATSP instance whose induced weight function wI equals w′ . To see this, recall that x is a primal optimal
solution and that (α, y) is a dual optimal solution (for (G, w)). Therefore complementary slackness implies that every set in L is tight with respect to x and that for every
edge (u, v) ∈ E(G′ ), the weight w′ (u, v) = w(u, v)−αu +αv equals the sum of yS -values for
the sets S crossed by (u, v). Finally, we have xe > 0 for every e ∈ E(G′ ) by definition. So
I satisfies all the properties of Definition 2.3, i.e., it is a laminarly-weighted instance.
We now argue that an α-approximate solution for I with respect to the Held-Karp
relaxation LP(G′ , w′ ) implies an α-approximate solution for the original instance (G, w)
with respect to LP(G, w). To this end, we make the following observation:
P
P
E(G′ )
Claim. For any Eulerian vector x ∈ R+ , we have e∈E(G′ ) w(e)x(e) = e∈E(G′ ) w′ (e)x(e).
Therefore the Held-Karp lower bound is the same for (G, w) and for (G′ , w′ ), and
any solution for (G′ , w′ ) is a solution of the same weight for (G, w).

8

S1

...

S2

v

u

Sℓ

(a)

(b)

Figure 2: (a) The structure of a tight set S with strongly connected components
S1 , . . . , Sℓ . Every path traversing S enters at a vertex in Sin ⊆ S1 , then visits
all strongly connected components, which form a “path” structure, before it
exits from a vertex in Sout ⊆ Sℓ .
(b) The structure of the path P from u ∈ Sin to v ∈ Sout for a tight set S as
given by Lemma 3.2. The path crosses the set that contains u but not v once
and it crosses the sets of L that are disjoint from {u, v} at most twice.
In the rest of the paper we work exclusively with laminarly-weighted ATSP instances I = (G, L, x, y). We will refer to these as simply instances. Recall that wI (F)
is the induced weight of an edge multiset F ⊆ E in the instance I. We will omit the
subscript and use simply w(F) whenever I is clear from the context. For a set S ⊆ V
we define
X
yR
valueI (S) = 2 ·
R∈L: R(S

to be the fractional dual value associated with the sets strictly inside S. Again, we will
omit the subscript whenever clear from the context. We also use value(I) = valueI (V);
note that this equals the Held-Karp lower bound of the instance. Indeed, as noted
above, y can be extended to an optimal dual solution to DUAL(G, w), and hence
P
the optimum value for DUAL(G, w) equals 2 · S∈L yS , which is equal to the primal
P
optimum value e∈E w(e)x(e) for LP(G, w) by strong duality.

3 Paths in Tight Sets
An instance I = (G, L, x, y) will be fixed throughout this section. We say that a path
P traverses a set S if both endpoints of P are in V \ S and P contains at least one vertex
in S. We now exhibit properties of paths traversing tight sets. In particular, we show
that the strongly connected components of a tight set S enjoy a nice path-like structure
as depicted in Figure 2.
Lemma 3.1. For a tight set S ( V we have the following properties:
(a) Every path from a vertex u ∈ Sin to a vertex v ∈ Sout (and thus every path traversing S)
visits every strongly connected component of S.
(b) For every u ∈ Sin and v ∈ S there is a path from u to v inside S. The same holds for every
u ∈ S and v ∈ Sout .
9

Proof. We remark that (a) can also be seen to follow from the “τ-narrow cut” structure
as introduced in [AKS15] by setting τ = 0. We give a different proof that we find
simpler for our setting.
Let S1 , S2 , . . . , Sℓ be the vertex sets of the strongly connected components of S,
indexed using a topological ordering. We thus have that each subgraph G[Si ] is
strongly connected and that there is no edge from a vertex in Si to a vertex in S j if i > j.
By the above, we must have δ− (S1 ) ⊆ δ− (S). Moreover, since x(δ− (S1 )) > 1 =
x(δ− (S)), we can further conclude that δ− (S1 ) = δ− (S) (recall that all edges have positive
x-value) and x(δ− (S1 )) = x(δ+ (S1 )) = 1 (i.e., S1 is a tight set).
Similarly, we can show by induction on k > 2 that
δ− (Sk ) = δ+ (Sk−1 )

and x(δ− (Sk )) = x(δ+ (Sk )) = 1.
S
To see this, note that δ− (Sk ) ⊆ δ− (S) ∪ i<k δ+ (Si ). However, δ− (S) = δ− (S1 ) (which is
disjoint from δ− (Sk )), and for i < k − 1, the induction hypothesis gives that δ+ (Si ) =
δ− (Si+1 ) (which is also disjoint from δ− (Sk )). The only term left in the union is i = k − 1
and so δ− (Sk ) ⊆ δ+ (Sk−1 ). Moreover, 1 6 x(δ− (Sk )) 6 x(δ+ (Sk−1 )) = 1, which implies the
statement for k.
Finally, we have that δ+ (Sℓ ) = δ+ (S). To recap, all incoming edges of S are into
S1 , the set of outgoing edges of every component is the set of incoming edges of the
next one, and all outgoing edges of S are from Sℓ . This shows (a), i.e., that every
path traversing S needs to enter through S1 , exit through Sℓ , and pass through every
component on the way.
Finally, (b) follows because Sin ⊆ S1 (similarly Sout ⊆ Sℓ ), each two consecutive
components are connected by an edge, and each component is strongly connected. 
Lemma 3.2. Let S ( V be a nonempty set such that L ∪ {S} is a laminar family. Suppose
u, v ∈ S are two vertices such that there is a path from u to v inside S. Then we can in
polynomial time find a path P from u to v inside S that crosses every set in L at most twice.
P
Thus, the path satisfies w(P) 6 R∈L: R(S 2 · yR = value(S).
In addition, if either u ∈ Sin or v ∈ Sout , then P P
crosses every tight set R ∈ L, R ( S at
most 2 − |R ∩ {u, v}| times. Thus, it satisfies w(P) 6 R∈L: R(S (2 − |R ∩ {u, v}|) · yR .
Proof. Since L ∪ {S} is a laminar family, any path inside S only crosses those sets R ∈ L
that have R ( S. Now, to prove both statements, it is enough to find, in polynomial
time, a path P inside S that for each R ∈ L with R ( S satisfies



2 if |R ∩ {u, v}| = 0,





1 if |R ∩ {u, v}| = 1,
|P ∩ δ(R)| 6 


2 if |R ∩ {u, v}| = 2,




0 if |R ∩ {u, v}| = 2 and either u ∈ Sin or v ∈ Sout .

The algorithm for finding P starts with any path P from u to v inside S. Such a
path is guaranteed to exist by the assumptions of the lemma and can be easily found
in polynomial time. Now, while P does not satisfy the above conditions, select a set
R ∈ L of maximum cardinality that violates one of the above conditions. We remark
that the selected set R is tight since R ∈ L. Therefore Lemma 3.1(b) implies that there is
10

a path from any u′ ∈ R to any v′ ∈ R inside R if either u′ ∈ Rin or v′ ∈ Rout . Using this,
the algorithm now modifies P depending on which of the above conditions is violated:
Case 1: |R ∩ {u, v}| = 0. Let u′ be the first vertex visited by P in R and let v′ be the last.
Then u′ ∈ Rin and v′ ∈ Rout , which implies by Lemma 3.1(b) that there is a path
Q from u′ to v′ inside R. We update P by letting Q replace the segment of P from
u′ to v′ . This ensures that the set R is no longer violated, since the path P now
only enters and exits R once.
Case 2: |R ∩ {u, v}| = 1. This case is similar to the previous one. Suppose that u ∈ R
and v < R (the other case is analogous). Let v′ be the last vertex visited by P in R.
Then v′ ∈ Rout , and again by Lemma 3.1(b) there is a path Q from u to v′ inside
R. We update P by letting Q replace the segment of P from u to v′ . This ensures
that the set R is no longer violated, since the path P now only exits R once.
Case 3: |R ∩ {u, v}| = 2. Let u′ be the first vertex visited by P in Rin . By Lemma 3.1(b),
there is a path Q from u′ to v inside R. We modify P by letting Q replace the
segment of P from u′ to v. This ensures that the set R is no longer violated, since
the path P now only enters and exits R at most once.
Case 4: |R ∩ {u, v}| = 2 and either u ∈ Sin or v ∈ Sout . Suppose that u ∈ Sin (the case v ∈
Sout is analogous). Then, as R ⊆ S, R ∩ Sin ⊆ Rin . So, by Lemma 3.1(b), there
is a path Q from u to v inside R. We replace P by Q and the set R is no longer
violated.
At termination, the above algorithm returns a path satisfying all the desired conditions and thus the lemma. It remains to argue that the algorithm terminates in
polynomial time. A laminar family contains at most 2n − 1 sets, so it is easy to efficiently identify a violated set R of maximum cardinality. The algorithm then, in
polynomial time, modifies P by simple path computations so that the set R is no longer
violated. Moreover, since the modifications are such that new edges are only added
within the set R, they may only introduce new violations to sets contained in R – sets
of smaller cardinality. It follows, since we always select a violated set of maximum
cardinality, that any set R in L is selected in at most one iteration. Hence, the algorithm
runs for at most |L| 6 2n − 1 iterations (and so it terminates in polynomial time).


4 Contracting and Inducing on a Tight Set
In this section we generalize two natural graph-theoretic constructions that allow one
to decompose the problem of finding a tour with respect to a vertex set S. The first relies
on contracting S (see Definition 4.2 in Section 4.1) and the second relies on inducing
on S (see Definition 4.6 in Section 4.2).

4.1 Contracting a Tight Set
Consider an instance I = (G, L, x, y). Before defining the contraction of a set S ∈ L,
we need to define the “distance” functions dS and DS . For S ∈ L and u, v ∈ S, define
11

A tour of the instance I/S

Instance I

S

5
2

The lift of the tour to a subtour of I

1

S

5
4
(u1in , s)

3
2

(s, v2out )

s

(u2in , s)

(u1in , v1in )

2

1

(u2out , v2out )

4
3

2

(s, v1out )

(u2in , v2in )

(u1out , v1out )

Figure 3: An example of the contraction of a tight set S and the lift of a tour. Only
y-values of the sets R ∈ L : R ⊆ S are depicted. On the left, only edges
that have one endpoint in S are shown. These are exactly the edges that
are incident to s in the contracted instance. In the center, a tour of I/S is
illustrated, and on the right we depict the lift of that tour.
dS (u, v) to be the minimum weight of a path inside S from u to v (if no such path exists,
dS (u, v) = ∞). We also let
X
X
DS (u, v) =
yR + dS (u, v) +
yR ,
R∈L: u∈R(S

R∈L: v∈R(S

P

which equals dS (u, v) + R∈L: R(S |R ∩ {u, v}| · yR . We remark that DS (u, u) might be
strictly positive.
The intuition of the definition of DS is as follows. After contracting S, all sets of the
laminar family are still present in the contracted instance, except for the sets strictly
contained in S. Now, after finding a tour in the contracted instance, we need to lift it
back to a subtour in the original instance. This is done as depicted in Figure 3: for each
visit of the tour to s (the vertex corresponding to the contraction of S) on the edges
(uiin , s), (s, viout ), we obtain a subtour of the original instance by replacing (uiin , s), (s, viout )
by the corresponding edges (i.e., by their preimages) (uiin , viin ), (uiout , viout ) of G together
with the minimum-weight path inside S from viin to uiout . The value DS (viin , uiout ) is the
weight increase incurred by this operation. For example, in Figure 3 we have
X
X
yR .
yR + dS (v1in , u1out ) +
DS (v1in , u1out ) =
| {z } R∈L: u1 ∈R(S
| {z } R∈L: v1 ∈R(S
out
in
=22
{z
}
|
{z
} =2+2·2+4+3 |
=3+4

=2

Before formally defining the notions of contraction and lift, we state the following
useful bound on DS (u, v).
Fact 4.1. For any u, v ∈ S with u ∈ Sin or v ∈ Sout we have
DS (u, v) 6 value(S).
12

Proof. Lemma 3.1(b) says that there is a path from u to v inside S. Select P to be the
path from u to v as guaranteed by Lemma 3.2. Since u ∈ Sin or v ∈ Sout , we have
X
(2 − |R ∩ {u, v}|) · yR
dS (u, v) 6 w(P) 6
R∈L: R(S

and thus
DS (u, v) = dS (u, v) +

X

|R ∩ {u, v}| · yR 6

R∈L:R(S

X

2 · yR = value(S) .

R∈L: R(S


We now define the notion of contracting a tight set for an ATSP instance. In short,
the contraction is the instance obtained by performing the classic graph contraction of S,
modifying L to remove the sets contained in S, and increasing the y-value of the new
singleton {s} corresponding to S so as to become yS + 1/2 maxu∈Sin ,v∈Sout DS (u, v). This
increase is done in order to pay for the maximum possible weight increase incurred
when lifting a tour in the contraction back to a subtour in the original instance (as
depicted in Figure 3, defined in Definition 4.4, and analyzed in Lemma 4.5).
Definition 4.2 (Contracting a tight set). The instance (G′ , L′ , x′ , y′ ) obtained from I =
(G, L, x, y) by contracting S ∈ L, denoted by I/S, is defined as follows:
– The graph G′ equals G/S, i.e., the graph obtained from G by contracting S. Let s
denote the new vertex of G′ that corresponds to the set S.
– For each edge e′ ∈ E(G′ ), x′ (e′ ) equals x(e), where e ∈ E(G) is the preimage of e′ in
G.3
– The laminar family L′ contains all remaining sets of L:
L′ = {R \ S ∪ {s} : R ∈ L, S ⊆ R} ∪ {R : R ∈ L, S ∩ R = ∅} .
– The vector y′ equals y (via the natural mapping) on all sets but {s}. For {s} we
define
y′s = yS +

1
max DS (u, v) .
2 u∈Sin ,v∈Sout

We remark that I/S as defined above is indeed an instance: L′ is a laminar family
of tight sets (since for each R ∈ L′ we have x′ (δ(R′ )) = x(δ(R)), where R is the preimage
of R′ in L via the natural mapping), y′R > 0 is defined only for R ∈ L′ , and x′ is a
feasible solution to LP(G′ , 0) that is strictly positive on all edges.
The way we defined the new dual weight y′s implies the natural property that the
value of the linear programming solution does not increase after contracting a tight
set:
3

Recall that for notational convenience we allow parallel edges in G/S and therefore the preimage is
uniquely defined.

13



Fact 4.3. value(I/S) = value(I) − valueI (S) − maxu∈Sin ,v∈Sout DS (u, v) 6 value(I).

Proof. By definition,

value(I/S) = 2 ·

X

y′R = 2 · y′s + 2 ·

R∈L′

X

yR

R∈L: R*S

=
=
=

max

u∈Sin ,v∈Sout

max

u∈Sin ,v∈Sout

max

u∈Sin ,v∈Sout

DS (u, v) + 2 · yS + 2 ·

X

yR

R∈L: R*S

DS (u, v) + 2 ·

X

yR − 2 ·

R∈L

X

yR

R∈L: R(S

DS (u, v) + value(I) − valueI (S)

and so the equality of the statement holds. Finally, the inequality of the statement
follows from Fact 4.1, which implies that maxu∈Sin ,v∈Sout DS (u, v) 6 valueI (S).

Having defined the contraction of a tight set S ∈ L, we define the aforementioned
operation of lifting a tour of the contracted instance I/S to a subtour in the original
instance I. When considering a tour (or a subtour), we order the edges according to
an arbitrary but fixed Eulerian walk. This allows us to talk about consecutive edges.
Definition 4.4. For a tour T of I/S, we define its lift to be the subtour of I obtained
from T by replacing each consecutive pair (uin , s), (s, vout ) of incoming and outgoing
edges incident to s by their preimages (uin , vin ) and (uout , vout ) in G, together with a
minimum-weight path from vin to uout inside S.4
See Figure 3 for an illustration. It follows that the lift is a subtour (i.e., an Eulerian
multiset of edges that forms a single component), because we added paths between
consecutive edges in the tour of I/S. However, the lift is usually not a tour of the
instance I, as it is not guaranteed to visit all the vertices in S. To extend the lift to a tour,
we use the concept of inducing on the tight set S, which we introduce in Section 4.2.
We complete this section by bounding the weight of the lift of T.
Lemma 4.5. Let T be a tour of the instance I/S. Then the lift F of T satisfies wI (F) 6 wI/S (T).
(1)

(1)

(k)

(k)

Proof. Consider the tour T and let (uin , s), (s, vout ), . . . , (uin , s), (s, vout ) be the edges that
(i)

T uses to visit the vertex s (which corresponds to the contracted set S). That is, (uin , s)
(i)

and (s, vout ) are the incoming and outgoing edge of the i-th visit of T to s. By the
definition of contraction, we can write the weight of T as
X
wI/S (T) =
αR yR + 2k · y′s
R∈L: R*S

=

X

αR yR + k · 2 · yS +

R∈L: R*S

max

u∈Sin ,v∈Sout

!
DS (u, v) ,

4
We remark that it is not really important that the minimum-weight path from vin to uout is selected
to be inside S; a minimum-weight path without this restriction would also work. We have chosen this
definition as we find it more intuitive and it simplifies some arguments.

14

(i)

(i)

where αR = |δ(R) ∩ T|. We now compare this weight to that of the lift F. Let (uin , vin )
(i)

(i)

(i)

(i)

and (uout , vout ) be the edges of G that are the preimages of (uin , s) and (s, vout ). The lift
(i)

(i)

(i)

(i)

(i)

(i)

F is obtained from T by replacing (uin , s), (s, vout ) by (uin , vin ), (uout , vout ) and adding a
(i)

(i)

minimum-weight path inside S from vin to uout . So F crosses every R ∈ L : R * S the
same number of times αR as T. To bound the weight incurred by crossing the tight
sets “inside” S, note that the i-th visit to the set S incurs a weight from crossing sets
R ∈ L : R ⊆ S that equals
X
X
(i) (i)
(i) (i)
yR = 2yS + DS (vin , uout ) .
yR + dS (vin , uout ) +
2yS +
(i)

(i)

R∈L: uout ∈R(S

R∈L: vin ∈R(S

Hence
wI (F) =

X

R∈L: R*S

6

X

k 
X

(i) (i)
αR yR +
2 · yS + DS (vin , uout )
i=1

αR yR +

R∈L: R*S

k
X
i=1

2 · yS +

max

u∈Sin ,v∈Sout

!
DS (u, v)

= wI/S (T) .


4.2 Inducing on a Tight Set
In this section we introduce our notion of induced instances. This concept will be
used for completing a lift of a tour of a contracted instance into a tour of the original
instance (see Definition 4.8 of “contractible” below). Inducing on a tight set S is similar
to contracting its complement V \ S into a single vertex s̄ (see Definition 4.2), though
the resulting laminar family and dual values are somewhat different: namely, we let
y′s̄ = value(S)/2 and we remove S (as well as all supersets of S) from L′ . The intuitive
reason for the setting of y′s̄ is that each visit to s̄ should pay for the most expensive
shortest paths in the strongly connected components of S (see Figure 4 and the proof
of Lemma 4.9).
We remark that the notion of inducing on S for ATSP instances differs compared to
the graph obtained by inducing on S (in the usual graph-theoretic sense), as here we
also have the vertex s̄ corresponding to the contraction of the vertices not in S. This is
needed to make sure that we obtain an ATSP instance (in particular, that we obtain a
feasible solution x′ to the linear programming relaxation).
Definition 4.6. The instance (G′ , L′ , x′ , y′ ) obtained from I = (G, L, x, y) by inducing
on a tight set S ∈ L, denoted by I[S], is defined as follows:
– The graph G′ equals G/S̄, i.e., the graph obtained from G by contracting S̄ = V \ S.
Let s̄ denote the new vertex of G′ that corresponds to the set S̄.

15

s̄
S1

S2

Figure 4: In the left figure we depict a tight set S ∈ L with two strongly connected
components S1 and S2 . The induced instance (right figure) is obtained by
contracting S̄ = V \ S into a vertex s̄ and removing the tight set S from
L. The solid edges are paths and edges of a tour in the induced instance.
In Lemma 4.9 we obtain an Eulerian set of edges in the original instance
(left figure) by adding the dashed paths, resulting in a tour of each strongly
connected component.
– For each edge e′ ∈ E(G′ ), x′ (e′ ) equals x(e), where e ∈ E(G) is the preimage of e′ in
G.5
– The laminar family L′ contains {s̄} and all sets that are strict subsets of S:
L′ = {R ∈ L : R ( S} ∪ {{s̄}} .
– The vector y′ equals y on the sets common to L′ and L. For the new set {s̄} we
define y′s̄ = value(S)/2.
We remark that I[S] in an instance: L′ is a laminar family of tight sets, y′R > 0 is
defined only for R ∈ L′ , and x′ is a feasible solution to LP(G′ , 0) that is strictly positive
on all edges.
As for the value of I[S], it is comprised of the y-values of sets strictly inside S, which
contribute value(S), and that of {s̄}, which also contributes 2y′{s̄} = value(S). Thus we
have
Fact 4.7. value(I[S]) = 2 value(S).
As alluded to above, we will use the instance I[S] to find an Eulerian multiset F of
edges of the original instance I such that F plus a lift of a tour in I/S form a tour of
the instance I. We say that such a set F makes S contractible:
Definition 4.8. We say that S ∈ L is contractible with respect to an Eulerian multiset
F ⊆ E of edges if the lift of any tour of I/S plus the edge set F is a tour of I.
As an example, if F were a subtour visiting every vertex of S, then S would be
contractible with respect to F. (Of course, such a subtour F can only exist if S is
strongly connected.) The following lemma shows that, in general, it is sufficient to
find a tour of I[S] in order to make S contractible (see also Figure 4).
5

We again recall that parallel edges are allowed in G/S̄, and thus the preimage of an edge is uniquely
defined.

16

Lemma 4.9. Given a tour T of I[S], we can in polynomial time find an Eulerian multiset of
edges F ⊆ E such that S is contractible with respect to F and wI (F) 6 wI[S] (T).
Proof. Let S1 , . . . , Sℓ be the strongly connected components of S indexed using a topological ordering. We will use T to obtain a low-weight tour Fi inside each Si , and define
F to be the union of these tours. Then S is contractible with respect to F. Indeed, the
lift of any tour of I/S must contain a path traversing S, and any such path visits every
connected component by Lemma 3.1(a).
Let us fix one component Si . We obtain the tour Fi of Si by reproducing the
movements of T inside Si (recall that we think of T as an ordered Eulerian walk). More
precisely, we retain those edges of T that are inside Si and, every time T exits Si on an
edge (uout , vout ) ∈ δ+ (Si ) and then returns to Si on an edge (uin , vin ) ∈ δ− (Si ), we also
insert a minimum-weight path from uout to vin inside Si . Such a path exists because Si
is strongly connected. (This step corresponds to adding the dashed paths in Figure 4.)
Then we set F = F1 ∪ . . . ∪ Fℓ .
It remains to show that F has low weight, i.e., that wI (F) 6 wI[S] (T). For this, let k
be the number of times the tour T visits the auxiliary vertex s̄. The weight incurred by
every such visit is at least 2y′s̄ = value(S) (since the set {s̄} is crossed twice in each visit).
Thus we have
wI[S] (T) > k · value(S) +

ℓ
X

wI[S] (T ∩ E(Si )) = k · value(S) +

i=1

ℓ
X

wI (T ∩ E(Si )) .

i=1

On the other hand, each tour Fi consists of all those edges of T that are inside Si , as
well as k shortest paths between some pairs of vertices in Si . Indeed, if T makes k
visits to the auxiliary vertex s̄, then we add exactly k paths inside Si due to the pathlike structure of the strongly connected components of a tight set S (Lemma 3.1). We
now have the following claim, which allows us to bound the length of these paths by
applying Lemma 3.2.
Claim. For each i = 1, . . . , ℓ, L ∪ {Si } is a laminar family.
Proof. Suppose toward a contradiction that L ∪ {Si } is not a laminar family. Then there
must be a set R ∈ L such that R \ Si , Si \ R, and S ∩ R are all non-empty. Furthermore,
since L is a laminar family and Si ⊆ S ∈ L, we must have R ( S. We can thus partition
R into the three sets
R<i = R ∩ (S1 ∪ · · · ∪ Si−1 ),

Ri = R ∩ Si ,

R>i = R ∩ (Si+1 ∪ · · · ∪ Sℓ ) .

In words, R<i is the part of R that intersects vertices of the strongly connected components that are ordered topologically before Si . Similarly, R>i is the part of R that
intersects vertices of the strongly connected components that are ordered topologically after Si . Note that since R is not contained in Si , we have that either R<i or R>i is
non-empty. We suppose R<i , ∅ (the case R>i , ∅ is analogous).
As x is a feasible solution to LP(G, 0), we have x(δ− (R<i )) > 1. Moreover, since
δ(Ri ∪ R>i , R<i ) = ∅ due to the topological ordering, we have δ− (R<i ) ⊆ δ− (R) and thus
1 = x(δ− (R)) > x(δ− (R<i )) + x(δ(Si \ Ri , Ri )) > 1 + x(δ(Si \ Ri , Ri )) ,
17

where the first equality follows since R ∈ L is a tight set. However, this is a contradiction because x(δ(Si \ Ri , Ri )) > 0; that holds since Si \ Ri = Si \ R , ∅ and Ri , ∅, Si
is a strongly connected component, and G only contains edges with strictly positive
x-value.
⋄
By the above claim, we can apply Lemma 3.2 to obtain that a shortest path between
two vertices inside Si has weight at most value(Si ). Recall that Fi consists of all those
edges of T that are inside Si , as well as k shortest paths between some pairs of vertices
in Si . Therefore, the weight of F is
wI (F) =

6

ℓ
X

i=1
ℓ
X

wI (Fi )
[k · value(Si ) + wI (T ∩ E(Si ))]

i=1

6 k · value(S) +

ℓ
X

wI (T ∩ E(Si ))

i=1

6 wI[S] (T) ,
as required.



5 Reduction to Irreducible Instances
In this section we reduce the problem of approximating ATSP on general (laminarlyweighted) instances to that of approximating ATSP on irreducible instances. Specifically, Theorem 5.3 says that any approximation algorithm for irreducible instances can
be turned into an algorithm for general instances while losing only a constant factor
in the approximation guarantee.
We now define the notions of reducible sets and irreducible instances. The intuition
behind them is as follows. The operations of contracting and inducing on a tight set S
introduced in the last section naturally lead to the following recursive algorithm:
1. Select a tight set S ∈ L.
2. Find a tour TS in the induced instance I[S]. Via Lemma 4.9, TS yields a set FS
that makes S contractible.
3. Recursively find a tour T in the contraction I/S.
4. Output FS plus the lift of T.
For this scheme to yield a good approximation guarantee, we need to ensure that we
can find a good approximate tour TS in I[S] and that contracting the set S results in a
“significant” decrease in the value of the LP solution. If it does, we refer to the set S as
reducible:

18

Definition 5.1. We say that a set S ∈ L is reducible if
max

u∈Sin ,v∈Sout

DS (u, v) < δ · value(S) ,

otherwise we say that S is irreducible. We also say that the instance I is irreducible if no
set S ∈ L is reducible.
We will use the value δ = 0.75; however, we keep it as a parameter to exhibit the
dependence of the approximation ratio on this value.
Note that singleton sets are never reducible. Moreover, we have the following
observation:
Fact 5.2. Consider an instance I = (G, L, x, y) and a set S ∈ L. If every set R ∈ L : R ( S is
irreducible, then I[S] is irreducible. In particular, if I is an irreducible instance, then I[S] is
irreducible for every S ∈ L.
Proof. Let I[S] = (G′ , L′ , x′ , y′ ). By definition, L′ = {R ∈ L : R ( S} ∪ {{s̄}}. Clearly,
the singleton set {s̄} is irreducible. Now consider a set R ∈ L : R ( S; we need to
show that R is irreducible in I[S]. Note that R is also present in I and that the sets
{Q ∈ L : Q ( R} and {Q ∈ L′ : Q ( R} are identical. This implies that the distance
function DR is identical in the instances I and I[S]. Moreover, the sets Rin and Rout are
also the same in the two instances. Therefore, as R is irreducible in I by assumption,
we have that R is also irreducible in I[S].

The above fact implies that if we select S ∈ L to be a minimal reducible set, then the
instance I[S] is irreducible. Hence, we only need to be able to find an approximate
tour TS for irreducible instances (in Step 2 of the above recursive algorithm). This is the
idea behind the following theorem, and its proof is based on formally analyzing the
aforementioned approach.
Theorem 5.3. Let A be a polynomial-time ρ-approximation algorithm for irreducible instances.
2ρ
Then there is a polynomial-time 1−δ -approximation algorithm for general instances.
Proof. Consider a general instance I = (G, L, x, y). If it is irreducible, we can simply
return the result of a single call to A. So assume that I is not irreducible, i.e., that L
contains a reducible set. Let S ∈ L be a minimal (inclusion-wise) reducible set, i.e., one
such that all subsets R ∈ L : R ( S are irreducible.
We will work with the induced instance I[S]. Recall that value(I[S]) = 2 value(S)
(Fact 4.7). Moreover, I[S] is irreducible by Fact 5.2. We can therefore use A to find a
tour TS of I[S]. Since A is a ρ-approximation algorithm, we have
wI[S] (TS ) 6 ρ · value(I[S]) = 2ρ value(S) .
Next, we invoke the algorithm of Lemma 4.9 to obtain an Eulerian multiset of
edges FS ⊆ E such that S is contractible with respect to FS and
wI (FS ) 6 wI[S] (TS ) 6 2ρ value(S) .

(5.1)

Now we recursively solve the contraction I/S. (This is a smaller instance than I,
because |I/S| = |I| − |S| + 1 and |S| > 2 since a singleton set S would not have been
19

reducible.) Let T be the tour obtained from the recursive call, and let F be the lift of T
to I. We finally return FS ∪ F. This is a tour of I, as S is contractible with respect to FS .
The running time of this algorithm is polynomial since each recursive call consists
at most of: one call to A, the algorithm of Lemma 4.9, simple graph operations and
one recursive call (for a smaller instance).
2ρ
Finally, let us show that this is a 1−δ -approximation algorithm by induction on the
instance size. We have
wI (F ∪ FS ) = wI (F) + wI (FS )
6 wI/S (T) + wI (FS )
2ρ
6
value(I/S) + 2ρ value(S)
1−δ
2ρ
[value(I) − (1 − δ) value(S)] + 2ρ value(S)
<
1−δ
2ρ
value(I),
=
1−δ
2ρ

where the first inequality is by Lemma 4.5, the second follows since T is a 1−δ approximate solution for I/S and by (5.1), and the strict inequality is by Fact 4.3
2ρ
and the reducibility of S. This shows that F ∪ FS is a 1−δ -approximate solution for
I.


6 Backbones and Reduction to Vertebrate Pairs
In this section we further reduce the task of approximating ATSP to that of finding a
tour in instances with a backbone. For an example of such an instance see the right part
of Figure 1 in the introduction.
Definition 6.1. We say that an instance I = (G, L, x, y) and a subtour B form a vertebrate
pair if every S ∈ L with |S| > 2 is crossed by B, i.e., δ(S) ∩ B , ∅. The set B is referred to
as the backbone of the instance.
Specifically, the main result of this section, Theorem 6.4, says that an algorithm
for vertebrate pairs can be turned into an approximation algorithm for irreducible
instances while losing only a constant factor in the guarantee. Combining this with
Theorem 5.3 allows us to reduce the problem of approximating ATSP on general
instances to that of approximating ATSP on vertebrate pairs.
The proof of Theorem 6.4 is done in two steps. First, in Section 6.1, we give an
efficient algorithm for finding a quasi-backbone B of an irreducible instance – a subtour
that crosses a large (weighted) fraction of the sets in L. We use the term quasi-backbone
as B might not cross all non-singleton sets, as would be required for a backbone. Then,
in Section 6.2, we give the reduction to vertebrate pairs via a recursive algorithm
(similar to the proof of Theorem 5.3 in the previous section).

20

The rerouting inside S when obtaining the quasi-backbone B from a lift
B′ of a tour T of the instance I′ obtained by contracting maximal sets
in L.

The lift F of the tour T ′ found in the
vertebrate pair (I′ , B), where I′ was
obtained by contracting R1 and R2 .

R2

The final tour T obtained by
adding results of recursive calls
on R1 and R2 (i.e., on I[R1 ] and
I[R2 ]).

R2

R2

vSmax

uSmax

uS

R1

R1

vS

R1

Figure 5: An illustration of the steps in the proofs of Lemma 6.3 (left) and Theorem 6.4
(center and right). Only one maximal set S ∈ L is shown.

6.1 Finding a Quasi-Backbone
We give an efficient algorithm for calculating a low-weight quasi-backbone of an irreducible instance.
Definition 6.2. For an instance I = (G, L, x, y), we call a subtour B a quasi-backbone if
X
yS 6 (1 − δ) value(I) ,
2
S∈L∗

where L∗ = {S ∈ L : δ(S) ∩ B = ∅} contains those laminar sets that B does not cross.
Recall that δ = 0.75 is the parameter in Definition 5.1 (of irreducible instances). Also
note that a backbone is not necessarily a quasi-backbone, as it may not satisfy the above
inequality if a lot of y-value is on singleton sets. Although the backbones we construct
do satisfy the inequality, we do not require this in the definition of the backbone
to simplify the presentation. Recall that αNW = 27 + ε denotes the approximation
guarantee for node-weighted instances given by Theorem 2.2.
Lemma 6.3. There is a polynomial-time algorithm that, given an irreducible instance I =
(G, L, x, y), constructs a quasi-backbone B such that w(B) 6 (αNW +3) value(I) and B∩δ(S) ,
∅ for every maximal non-singleton set S ∈ L.
Proof. Let Lmax be the family of all maximal sets in L. We define I′ to be the instance
obtained from I by contracting all sets in Lmax . By Fact 4.3, the LP value does not
increase, i.e., value(I′ ) 6 value(I). In I′ , all laminar tight sets are singletons, therefore
the new instance is node-weighted and we can use the αNW -approximation algorithm
(Theorem 2.2) to find a tour T in I′ with wI′ (T) 6 αNW value(I′ ) 6 αNW value(I).
Now, to obtain a subtour B of the original instance I, we consider the lift B′ of
T back to I (see Definition 4.4). The lift B′ is a subtour of low weight. Indeed,
wI (B′ ) 6 wI′ (T) 6 αNW value(I) by Lemma 4.5. It also crosses every maximal set
S ∈ Lmax . However, it might not yet satisfy the inequality of Definition 6.2. We
therefore slightly modify the subtour B′ to obtain B as follows. For each set S ∈ Lmax :
21

1. Suppose the first visit6 to S in the subtour B′ arrives at a vertex uS ∈ Sin and
departs from a vertex vS ∈ Sout .
2. Replace the segment of B′ from uS to vS by the union of:
– a shortest path from uS to uSmax ,
– a path from uSmax to vSmax inside S as given by Lemma 3.2,
– and a shortest path from vSmax to vS ,
where uSmax ∈ Sin and vSmax ∈ Sout are selected to maximize DS (uSmax , vSmax ).
See the left part of Figure 5 for an illustration. The existence of the second path above
is guaranteed by Lemma 3.1(b) since uSmax ∈ Sin . It is clear that the obtained multiset
B is a subtour (since B′ is a subtour), that it crosses every set in Lmax , and that the
algorithm for finding B runs in polynomial time. It remains to bound the weight of
B and to show that B satisfies the property of a quasi-backbone, i.e., the inequality of
Definition 6.2.
For the former, note that the weight of B is at most the weight of the lift B′ plus the
weight of the three paths added for each set S ∈ Lmax . For such a set S ∈ Lmax , the
weight of the path from uS to uSmax is at most value(S) since there is a path from uS ∈ Sin
to uSmax inside S by Lemma 3.1(b) and such a path can be selected to have weight at
most value(S) by Lemma 3.2. By the same argument, we have that the weight of the
path from vSmax to vS ∈ Sout is at most value(S). Finally, by applying Lemma 3.2 again,
we have that the path added from uSmax to vSmax is also bounded by value(S). It follows
that
X
w(B) 6 w(B′ ) + 3 ·
value(S) 6 w(B′ ) + 3 value(I) 6 (αNW + 3) value(I) ,
S∈Lmax

as required. (In the second inequality we used that the sets S ∈ Lmax are disjoint.)
We proceed to prove that B satisfies the inequality of Definition 6.2. Recall that
L∗ = {S ∈ L : δ(S) ∩ B = ∅} contains those laminar sets that B does not cross. As B
crosses every S ∈ Lmax (i.e., Lmax ∩ L∗ = ∅), it is enough to show the following:
Claim. For every S ∈ Lmax we have
X

2yR 6 (1 − δ) value(S) .

R∈L∗ : R(S

Once we have this claim, the property of a quasi-backbone indeed follows:
X
X
X
X
(1 − δ) value(S) 6 (1 − δ) value(I) .
yR =
2yR 6
2
R∈L∗

S∈Lmax R∈L∗ : R(S

S∈Lmax

Proof of Claim. The intuition behind the claim is that, when forming B, we have added
a path P from uSmax to vSmax . Since S is irreducible, this path P has a large weight.
However, it is chosen so that it crosses each set in L at most twice. Thus it must cross
most (weighted by value) sets of L contained in S.
6

Recall that the edges of the subtour B′ are ordered by an Eulerian walk.

22

Now we proceed with the formal proof. As uSmax ∈ Sin , the path P inside S from
to vSmax that we have obtained from Lemma 3.2 crosses every tight set R ∈ L at
most 2 − |R ∩ {uSmax , vSmax }| times. Moreover, P (a subset of B) does not cross any set
R ∈ L∗ . Therefore
X


dS (uSmax , vSmax ) 6 w(P) 6
2 − |R ∩ {uSmax , vSmax }| · yR .

uSmax

R∈L\L∗ : R(S

Furthermore, we have that the quasi-backbone B crosses all sets in Lmax and visits both
vertices uSmax and vSmax . Therefore it must cross all sets R ∈ L for which R ∩ {uSmax , vSmax }
is non-empty; i.e., for all R ∈ L∗ we have |R ∩ {uSmax , vSmax }| = 0. It follows that that the
quasi-backbone crosses most (weighted by value) laminar sets:
X
X
X
2yR =
(2 − |R ∩ {uSmax , vSmax }|) · yR +
|R ∩ {uSmax , vSmax }| · yR
R∈L\L∗ : R(S

R∈L\L∗ : R(S

R∈L\L∗ : R(S

> dS (uSmax , vSmax ) +

X

|R ∩ {uSmax , vSmax }| · yR

R∈L: R(S

=

DS (uSmax , vSmax )

> δ value(S) ,
where the last inequality is by the choice of uSmax , vSmax and by the irreducibility of S.
The claim now follows:
X
X
2yR = value(S) −
2yR 6 value(S) − δ value(S) = (1 − δ) value(S) .
R∈L∗ : R(S

R∈L\L∗ : R(S

⋄
The proof of the above claim completes the proof of Lemma 6.3.



6.2 Obtaining a Vertebrate Pair via Recursive Calls
We now prove the main result of Section 6.
Theorem 6.4. Let A be a polynomial-time algorithm that, given a vertebrate pair (I′ , B),
returns a tour of I′ with weight at most κ value(I′ )+ηwI′ (B) (for some κ, η > 0). Then there is
κ+η(αNW +3)
a polynomial-time ρ-approximation algorithm for irreducible instances, where ρ = 1−2(1−δ)
.
The proof of this theorem is somewhat similar to that of Theorem 5.3, in that the
algorithm presented here will call itself recursively on smaller instances, as well as
invoking the black-box algorithm A (once per recursive call).
Proof. We briefly discuss the intuition first. Consider an irreducible instance I =
(G, L, x, y). By Lemma 6.3, we can find a quasi-backbone B – a subtour such that
P
∗
S∈L∗ 2yS 6 (1 − δ) value(I), where as before L = {S ∈ L : δ(S) ∩ B = ∅} contains
the laminar sets that the quasi-backbone does not cross. This is a small fraction of
the entire optimum value(I), so we can afford to run an expensive procedure (say,
23

a 2ρ-approximation) on the unvisited sets (using recursive calls) so as to make them
contractible. Once we contract all these sets, B will become a backbone in the contracted
instance and we will have thus obtained a vertebrate pair, on which the algorithm A
can be applied.7 See Figure 5 for an illustration.
We now formally describe the ρ-approximation algorithm Airr for irreducible instances. Given an irreducible instance I = (G, L, x, y), it proceeds as follows:
1. Invoke the algorithm of Lemma 6.3 to obtain a quasi-backbone B with wI (B) 6
(αNW + 3) value(I). Denote by L∗max the family of maximal (inclusion-wise) nonsingleton sets in L∗ = {S ∈ L : δ(S) ∩ B = ∅}. (For example, in Figure 5, R1 and R2
are two such sets.)
2. For each S ∈ L∗max , recursively call Airr to find a tour TS in the instance I[S]
(which is irreducible by Fact 5.2). Then use TS and the algorithm of Lemma 4.9
to find an Eulerian multiset of edges FS such that S is contractible with respect
to FS and wI (FS ) 6 wI[S] (TS ).
3. Let I′ be the instance obtained from I by contracting all the maximal sets
S ∈ L∗max . We have that (I′ , B) is a vertebrate pair by construction: we have
contracted all tight sets that were not crossed by B into single vertices, and so
B is a backbone of I′ . We can therefore invoke the algorithm A on (I′ , B). By
assumption, this returns a tour T′ of I′ such that w(T′ ) 6 κ value(I′ ) + ηwI′ (B) .
S
4. Finally, return the tour T consisting of the lift F of T′ to I together with S∈L∗max FS .
(See the center and right parts of Figure 5 for an illustration.)
We remarkSthat T is indeed a tour of I since all sets S ∈ L∗max are contractible with
respect to S∈L∗max FS .
Having described the algorithm, it remains to show that Airr runs in polynomial
time and that it has an approximation guarantee of ρ.
For the former, we bound the total number of recursive calls that Airr makes. We
claim that the total number of recursive calls on input I = (G, L, x, y) is at most the
cardinality of L>2 = {S ∈ L : |S| > 2}. The proof is by induction on |L>2 |. For the
base case, i.e., when |L>2 | = 0, there are no recursive calls since there are no nonsingleton sets in L∗ ⊆ L and so L∗max = ∅. For the inductive step, suppose that
L∗max = {S1 , S2 , . . . , Sℓ } ⊆ L∗ and so there are ℓ recursive calls in this iteration – on the
instances I[S1 ], I[S2 ], . . . , I[Sℓ ]. If we let Li>2 denote the non-singleton laminar sets
of I[Si ] then, by the definition of inducing on a tight set, for every R ∈ Li>2 we have
R ( Si and R ∈ L>2 . It follows by the induction hypothesis that the total number of
recursive calls that Airr makes is
ℓ+

ℓ
X

|Li>2 | 6 ℓ + |L>2 | − ℓ = |L>2 | ,

i=1

where the inequality holds because the sets Li>2 are disjoint and L1>2 ∪ L2>2 ∪ · · · ∪ Lℓ>2 ⊆
L>2 \{S1 , S2 , . . . , Sℓ }. Hence, the total number of recursive calls Airr makes is |L>2 | 6 |L|,
7

Note that we never actually find a backbone of the original, uncontracted instance.

24

which is at most linear in |V|. The fact that Airr runs in polynomial time now follows
because each call runs in polynomial time. Indeed, the algorithm of Lemma 6.3, the
algorithm of Lemma 4.9, and A all run in polynomial time.
We now complete the proof of the theorem by showing that Airr is a ρapproximation algorithm. We have by the assumptions on A and by Lemma 4.5
that the weight wI (F) of the lift F of T′ is at most
wI′ (T′ ) 6 κ value(I′ )+ηwI′ (B) 6 κ value(I)+η(αNW +3) value(I) = (κ+η(αNW +3)) value(I) ,
where the second inequality follows by Fact 4.3 and since wI′ (B) = wI (B) (I′ arises by
contracting only sets not visited by B, which preserves the weight of B) and wI (B) 6
(αNW + 3) value(I).

S
Now, to show that w(T) = w(F) + w S∈L∗max FS 6 ρ value(I), we proceed by
induction on the total number of recursive calls. In the base case, when no recursive
calls are made, we have w(T) = w(F) 6 wI′ (T′ ) 6 (κ + η(αNW + 3)) value(I) 6 ρ value(I).
For the inductive step, the induction hypothesis yields that for each S ∈ L∗max we have
w(FS ) 6 wI[S] (TS ) 6 ρ value(I[S]) = 2ρ value(S) ,
where the equality is by Fact 4.7. Hence


X
X

 [


2ρ value(S)
w(FS ) 6
FS  =
w 

 ∗
∗
∗
S∈L
S∈Lmax
S∈Lmax
X max
X
X
2ρ
2yR 6 2ρ
2yR 6 2ρ(1 − δ) value(I) .
=
S∈L∗max

R∈L∗ : R(S

R∈L∗

The second equality holds because Lemma 6.3 guarantees that B crosses each maximal
set of L, which implies that everyPR ∈ L that is a subset
of a set S ∈ L∗max is not crossed
P
by B, i.e., R ∈ L∗ : thus we have R∈L: R(S 2yR = R∈L∗ : R(S 2yR for all S ∈ L∗max . The
last inequality holds because B is a quasi-backbone
of I (see Definition 6.2). Summing
S
up the weight of the lift F of T′ and of S∈L∗max FS we get

w(T) 6 κ + η(αNW + 3) + 2ρ(1 − δ) value(I) = ρ value(I) ,
by the selection of ρ to equal
proof of the theorem.

κ+η(αNW +3)
1−2(1−δ) .

This concludes the inductive step and the


7 Algorithm for Vertebrate Pairs
In this section we consider a vertebrate pair (I, B) and prove the following theorem.
This provides the algorithm required in Theorem 6.4.
Theorem 7.1. Let (I, B) be a vertebrate pair8 . For every ε > 0 there is a polynomial-time
algorithm that returns a tour T of I with w(T) 6 8(9 + ε) · value(I) + (9 + ε) · w(B).
8
Throughout this section we will assume that B , ∅. In the special case when B = ∅, it must be the
case that L>2 = ∅ and thus the instance is node-weighted; we can simply apply the αNW -approximation
algorithm of Theorem 2.2.

25

Recall that value(I) equals the Held-Karp lower bound. This theorem, together
with Theorem 6.4, yields a constant-factor approximation algorithm for any irreducible instance. Combined with the reductions of the previous sections, this implies
a constant-factor approximation algorithm for arbitrary instances. We provide an
overview of the entire sequence of reductions in Section 8.
Our algorithm for vertebrate pairs uses the approach introduced in [Sve15] that
reduces the problem of finding a tour in I to that of solving the Local-Connectivity
ATSP problem on I. We first define the necessary concepts from [Sve15] in Section 7.1.

7.1 Local-Connectivity ATSP
The Local-Connectivity ATSP problem consists in finding “local” subtours that are
only required to cross the sets of a given partition V = V1 ∪ · · · ∪ Vk of the vertices
instead of connecting the entire graph (as in the standard ATSP). A “good” solution to
Local-Connectivity ATSP has a local requirement: each subtour should not be much
more expensive than the lower bound on the cost of visiting the vertices in the subtour
(see the definition of lightness below).
That lower bound on the cost of visiting vertices is defined in terms of a “lower
bound” function lb : V → R+ . The only requirement besides non-negativity is that the
lb function needs to be fixed by our algorithm (as a function of the instance I and the
backbone B) before it is allowed to access the given partition. In order to emphasize the
relationship between the solution quality (see the definition of α-lightness below) of
our algorithm for Local-Connectivity ATSP and the final approximation guarantee for
ATSP, we additionally assume the normalization lb(V) 6 value(I) (see [Sve15, Remark
3.1]).
Intuitively, lb(v) encodes how much we are willing to pay to visit vertex v. For
a vertebrate pair (I, B), we select lb as follows. Let V(B) denote the vertices that are
incident to an edge in B, and define

1


value(I)
 |V(B)| (value(I) + w(B)/4) if v ∈ V(B),
lb(v) = lb(v) ·
,
where
lb(v) = 

2yv
otherwise.
lb(V)

Note that lb is merely a version of lb scaled down so that lb(V) = value(I). For
notational convenience we extend the vector y to all singletons so that yv = 0 if {v} < L.
We also note that the reason for our particular choice of lb is to simplify the calculations
in the proof of Lemma 7.6.
For an edge multiset F let C(F) denote the set of strongly connected components
of (V, F). Note that if F is Eulerian, then every component of (V, F) that is connected in
the undirected sense is also strongly connected, and the edge set of every component
forms a (possibly empty) subtour.
We now formally define the Local-Connectivity ATSP problem, having fixed the
lower bound function lb as e.g. above. The input is a partition V = V1 ∪ V2 ∪ . . . ∪ Vk
of the vertices (k > 2), and the output an Eulerian multisubset F⋆ of E such that
|δ−F⋆ (Vi )| > 1 for i = 1, 2, . . . , k .
26

(Recall that δ−F⋆ (Vi ) = δ− (Vi ) ∩ F⋆ .) We say that an algorithm for Local-Connectivity
ATSP is α-light on I (with respect to lb) if, for any input V1 ∪ · · · ∪ Vk , the algorithm
finds an Eulerian edge set F⋆ such that
w(G̃) 6 α · lb(G̃)

for every component G̃ ∈ C(F⋆ ).

Here we use the notation that for a connected component
G̃ of (V, F⋆ ), w(G̃) =
P
P
e∈E(G̃) w(e) (summation over the edges) and lb(G̃) =
v∈V(G̃) lb(v) (summation over
the vertices).
The main technical theorem of [Sve15] reduces the problem of finding a tour to
that of solving Local-Connectivity ATSP, up to a constant factor.
Theorem 7.2 ([Sve15, Theorem 5.1]). Suppose that there is an algorithm A for LocalConnectivity ATSP that is α-light on I. Then there exists a tour of I of weight at most
5α value(I). Moreover, for any ε > 0 a tour of weight at most (9 + ε)α value(I) can be found
in time polynomial in the number n = |V| of vertices, in 1/ε, and in the running time of A.
To show Theorem 7.1, it thus suffices to devise a polynomial-time algorithm for
Local-Connectivity ATSP that is α-light on I, where α = 8 + w(B)/value(I).9 This gives a
tour of weight at most (9 + ε)α value(I) = (9 + ε) (8 value(I) + w(B)), as required.

7.2 The Algorithm for Vertebrate Pairs
We now formulate our main technical lemma. Let L>2 denote the family of nonsingleton sets in L. Recall that for an Eulerian multiset F ⊆ E, the edge set of each
component in C(F) is a subtour. We refer to them as the subtours in F.
Lemma 7.3. There is a polynomial-time algorithm that solves the following problem. Let (I, B)
be a vertebrate pair, and let U1 , . . . , Uℓ ⊆ V \ V(B) be disjoint non-empty vertex sets such that
the subgraphs G[U1 ], . . . , G[Uℓ ] are strongly connected and for every S ∈ L>2 and i = 1, . . . , ℓ
we have either Ui ∩ S = ∅ or Ui ⊆ S. Then the algorithm finds an Eulerian multiset F ⊆ E of
edges such that:
(a) w(F) 6 3 · value(I),
(b) |δ−F (Ui )| > 1 for every i = 1, . . . , ℓ,
(c) |δ−F (v)| 6 4 for every v ∈ V with x(δ− (v)) = 1,
(d) any subtour in F that crosses a tight set in L>2 visits a vertex of the backbone.
The proof will be given in Section 7.3. It uses an auxiliary split graph: a concept
inspired by the authors’ previous work on ATSP on graphs with two different edge
weights [STV16]. Let us give an informal explanation of the statement before we
use it for Local-Connectivity ATSP. The requirements on the disjoint sets U1 , . . . , Uℓ
are that they do not contain any vertex of the backbone, they are strongly connected,
and L>2 ∪ {U1 , . . . , Uℓ } is a laminar family in which the sets U1 , . . . , Uℓ are minimal
9
To be precise, for a polynomial running time we should also be able to evaluate the lb function in
polynomial time, which clearly is the case here.

27

S

Ui

Vi

Figure 6: On the left, the “dotted” sets U1 , . . . , Uℓ of Lemma 7.3 are depicted.
On the right, we show how the set Ui is obtained by the algorithm for
Local-Connectivity ATSP in Section 7.2: Vi is intersected with a minimal
non-singleton set S to obtain Vi′ (the striped area). Then Ui is a source
component in the decomposition of Vi′ into strongly connected components.
This implies that there are no edges from Vi′ \ Ui to Ui and so any edge in
δ(Vi \ Ui , Ui ) must come from outside of Vi′ and thus cross the tight set S.
(see the left part of Figure 6). Now, given such sets, the lemma says that there is a
polynomial-time algorithm which outputs an Eulerian multiset F of edges that (a) is
of low weight, (b) crosses all the sets U1 , . . . , Uℓ (similarly to the requirement for a
solution to Local-Connectivity ATSP), and (c) visits every tight vertex at most four
times. Finally, we also have that (d) any subtour in F that crosses a non-singleton tight
set intersects the backbone. This property will be important for analyzing the lightness
of our tour. Indeed, it will imply that any connected component of our solution F⋆ to
Local-Connectivity ATSP that is disjoint from the backbone does not cross a set in L>2 .
So any edge (u, v) in such a component will have weight equal to yu + yv . Intuitively,
this (almost) reduces the problem to the node-weighted case.
Description of algorithm. Equipped with Lemma 7.3, we are ready to describe our
algorithm for Local-Connectivity ATSP. Let V = V1 ∪ · · · ∪ Vk be the input, i.e., a
partition of V into k > 2 sets. Our output F⋆ = B ∪ P ∪ F will consist of three Eulerian
multisets of edges. The first set is the backbone B itself. The set P is selected so as
to handle the special case of the backbone being fully inside a single partition class:
in that case, P will cross that partition class. Finally, F is selected so as to cross any
partition class whose vertices are disjoint from the vertices of the backbone. They are
obtained as follows:
(P) If there is no partition class that contains all the vertices of the backbone, then
we set P = ∅. Otherwise, let Vi be the partition class with V(B) ⊆ Vi . We
select arbitrary vertices u ∈ V(B) and v ∈ V \ Vi , and we let P be the edges of
a minimum-weight path from u to v plus the edges of a minimum weight path
from v to u.
(F) For convenience, index the partition classes so that V1 , . . . , Vℓ are those sets that
are disjoint from the vertices of the backbone (we have 0 6 ℓ < k). For i = 1, . . . , ℓ
let Vi′ be the intersection of Vi with a minimal set S ∈ L>2 ∪ {V} with S ∩ Vi , ∅.
Then consider a decomposition of Vi′ into strongly connected components (with
28

respect to G[Vi′ ]). Let Ui ⊆ Vi′ be the vertex set of a source component in this
decomposition. That is, there is no edge from Vi′ \ Ui to Ui in G (see also the
right part of Figure 6). By construction, the sets U1 , . . . , Uℓ satisfy the conditions
of Lemma 7.3; in particular, Vi′ (and thus Ui ) is a subset of the minimal set S
chosen above, which makes Ui a subset of any laminar superset of S and disjoint
from any laminar set that is not a superset of S. We let F be the Eulerian multiset
guaranteed by Lemma 7.3.
This completes the description of our algorithm for Local-Connectivity ATSP. We
proceed to its analysis.
Remark 7.4. One can improve the guarantee of the above algorithm by using a slightly
more complex procedure and modifying the definition of lb. Namely, one can show
that either of the two sets B and P is always sufficient.
7.2.1

Analysis

It is clear that the algorithm runs in polynomial time: B is provided in the input, P is
either the empty set or the union of two minimum-weight paths, and F is obtained via
the polynomial-time algorithm guaranteed by Lemma 7.3. In addition, the solution
F⋆ = B ∪ P ∪ F is Eulerian, since B, P, and F are all Eulerian. It remains to show that
F⋆ crosses every set of the input (Lemma 7.5) and that it is α-light (Lemma 7.6 and
Corollary 7.7).
Lemma 7.5. We have |δ−F⋆ (Vi )| > 1 for i = 1, 2, . . . , k.
Proof. We first consider a partition Vi that intersects the backbone, i.e., Vi ∩ V(B) , ∅.
If V(B) * Vi , then B (and thus F⋆ ) crosses Vi . Otherwise, in the special case when
V(B) ⊆ Vi , P is defined so that it enters Vi .
Let us now consider the more interesting case of Vi being disjoint from the vertices
of the backbone, i.e., V(B) ∩ Vi = ∅ (and i 6 ℓ). By property (b) of Lemma 7.3, there
exists an edge e ∈ δ−F (Ui ). Then either e ∈ δ−F (Vi ) (in which case we are done since
F ⊆ F⋆ ), or e ∈ δF (Vi \ Ui , Ui ). Assume the latter case.
Using that Ui was a source component in the decomposition of Vi′ into strongly
connected components, e must enter a set in L>2 . Indeed, recall that Ui was selected so
that there is no edge from Vi′ \ Ui to Ui . Since e ∈ δF (Vi \ Ui , Ui ) and δ(Vi′ \ Ui , Ui ) = ∅, we
must have e ∈ δ(Vi \ Vi′ , Ui ) ⊆ δ(Vi \ Vi′ , Vi′ ). However, Vi′ was obtained by intersecting
Vi with a minimal set S ∈ L>2 ∪ {V} with S ∩ Vi , ∅. Thus we must have e ∈ δ−F (S) (and
S , V). Now, property (d) of Lemma 7.3 guarantees that the connected component
(i.e., the subtour) of F containing e must visit V(B). This subtour thus visits both Vi
(the head of e is in Ui ⊆ Vi ) and V(B), which is disjoint from Vi . As such, the subtour

must cross Vi , i.e., we have |δ−F⋆ (Vi )| > |δ−F (Vi )| > 1 as required.
Lemma 7.6. For every connected component G̃ of (V, F⋆ ), i.e., G̃ ∈ C(F⋆ ), we have
w(G̃) 6 4 lb(G̃) .

29

Proof. Recall that the backbone B is a subtour, which means that it forms a single
component. Therefore, since B ⊆ F⋆ , there is one component of (V, F⋆ ) that contains
the backbone and the others are disjoint from the backbone.
First suppose that G̃ is the component that contains the backbone. Then
lb(G̃) > lb(V(B)) = 1/4 · w(B) + value(I) ,
whereas
w(G̃) 6 w(F⋆ ) = w(B) + w(P) + w(F) 6 w(B) + w(P) + 3 · value(I) ,
where we used that w(F) 6 3 · value(I) by property (a) of Lemma 7.3. Hence w(G̃) 6
4 lb(G̃) will follow once we show that w(P) 6 value(I). This is trivially true if P = ∅.
Otherwise, i.e., if P is selected as the union of two minimum-weight paths, we have
the following claim.
Claim. For any two vertices u, v ∈ V, the total weight of the minimum-weight u − v
path and the minimum-weight v − u path is at most value(I).
Proof of Claim. We will show that x simultaneously supports one unit of flow from u
to v and one unit of flow from v to u. The subtour elimination constraints in LP(G, w)
guarantee the existence of a unit flow f from u to v (by the min-cut max-flow theorem).
Consider the flow x′ = x − f ; we claim that x′ (δ− (S)) > 1 holds for every S ⊆ V \ {v}
with u ∈ S, and therefore we can find another unit flow 1 from v to u such that f + 1 6 x.
Indeed, x(δ+ (S)) = x(δ− (S)) since x is Eulerian, and f (δ+ (S)) = f (δ− (S)) + 1. Hence
x′ (δ− (S)) = x′ (δ+ (S)) + 1 > 1.
Now the claim follows since the weight of a minimum-weight u − v path is at most
the weight of f , and similarly for the v − u path and 1. Since f + 1 6 x, their total weight
is at most that of x, i.e., value(I).
⋄
Now consider the case when G̃ is disjoint from the backbone. For the lower bound,
we have
X
X
lb(G̃) =
lb(v) = 2
yv .
v∈V(G̃)

v∈V(G̃)

To bound the weight of G̃, note that G̃ does not contain any edges of B or P (recall that
P, if non-empty, has an edge incident to a vertex u ∈ V(B)). Moreover, by property (d)
of Lemma 7.3, the edges of G̃ (which is a subtour in F) do not cross any tight set in L>2 .
Therefore any edge (u, v) ∈ E(G̃) has weight yu + yv and so
X
X
X
w(G̃) =
w(e) =
|δG̃ (v)|yv 6 8
yv = 4 lb(G̃) ,
e∈E(G̃)

v∈V(G̃)

v∈V(G̃)

where for the inequality we used that yv is only strictly positive if x(δ− (v)) = 1 (see
Definition 2.3), in which case |δG̃ (v)| = |δF (v)| = 2|δ−F (v)| 6 8 using property (c) of

Lemma 7.3.
Corollary 7.7. The algorithm is (8 + w(B)/value(I))-light (with respect to lb).

30

Proof. Lemma 7.6 implies
w(G̃) 6 4 lb(G̃) = 4 ·

lb(V)
· lb(G̃).
value(I)

Furthermore,10
lb(V) = value(I) +

w(B)
+
4

X

v∈V\V(B)

2yv 6 2 value(I) +

w(B)
.
4


We have thus given a polynomial-time algorithm for Local-Connectivity ATSP for
vertebrate pairs (I, B) that is (8 + w(B)/value(I))-light. Together with Theorem 7.2 this
implies Theorem 7.1, the main result of this section.
The only missing ingredient now is a proof of the main technical Lemma 7.3. We
devote Section 7.3 to it.

7.3 The Split Graph
The main step in the proof of Lemma 7.3 is to solve a circulation problem in an auxiliary
graph that we construct in two steps. First, for the given instance I, we define the
split graph. In the second step, we further modify the split graph, taking the input
U1 , U2 , . . . , Uℓ of Lemma 7.3 into account.
Recall that L>2 denotes the family of non-singleton sets in L. Let us use an indexing
L>2 ∪ {V} = {S1 , S2 , . . . , Sℓ } such that 2 6 |S1 | 6 |S2 | 6 · · · 6 |Sℓ | = |V|. For a vertex v ∈ V
let
level(v) = min{i : v ∈ Si }
be the index of the first (smallest) set that contains v. We use these levels to define a
partial order ≺ on the vertices: let v ≺ v′ if level(v) < level(v′ ). This partial order is
used to classify the edges as follows. An edge (u, v) ∈ E is a
– forward edge if v ≺ u,
– backward edge if u ≺ v,
and otherwise it is a neutral edge. Let E f , Eb and En denote the sets of forward,
backward, and neutral edges respectively.
The idea behind the split graph and the three edge types is the following. We
would like to ensure the crucial property (d) of Lemma 7.3, which is roughly that, in
the solution F, any cycle that crosses a set in L>2 must then also visit the backbone.
Note that such a cycle must contain both a forward and a backward edge. For consider
the cyclic sequence of levels of vertices in the cycle: it is not constant, therefore it
must both increase and decrease at some points. Now, we will guarantee property (d)
10
We note that a tighter bound could be given if we used that the backbone
P B had been obtained via
a quasi-backbone (see Section 6), in which case one could conclude that 2 v∈V\V(B) yv 6 (1 − δ) value(I).
We keep the weaker bound for simplicity.

31

G and L>2 = {S1 , S2 , S3 }

Gsp
a0

S3

a

d

S2

d0
a1

d1

b0

S1

b

e

c

f

e0
b1

e1

f0

c0
c1

f1

Figure 7: An example of the construction of Gsp from G, L>2 , and the backbone B. The
vertices of the backbone are depicted in black. On the left, the forward edges
are straight, the backward edges are swirly, and the neutral edges are dashed.
On the right, the edges of Gsp without a preimage in G are dotted.
by splitting each vertex v into two copies v0 and v1 and forcing forward edges to go
between the 1-vertices and backward edges to go between the 0-vertices. Since our
cycle contains both types, its version in the split graph will visit both 0-vertices and
1-vertices. Clearly, it will need to also contain an edge from a 1-vertex to a 0-vertex.
But, crucially, in the split graph the only such edges will be of the form (v1 , v0 ) for
backbone vertices v ∈ V(B). This will guarantee that the cycle visits the backbone. (See
Fact 7.9 for a formal statement and proof of this claim.)
Now we define the split graph (see Figure 7 for an example):
Definition 7.8. The split graph Gsp is defined as follows. For every v ∈ V we create two
copies v0 and v1 in V(Gsp ). The edge set E(Gsp ) contains the following edges:
– For every v ∈ V \ V(B) we create an edge (v0 , v1 ) of weight 0.
– For every v ∈ V(B) we create edges (v0 , v1 ) and (v1 , v0 ) of weight 0.
– For every forward edge (u, v) ∈ E f we create an edge (u1 , v1 ) of weight w(u, v).
– For every backward edge (u, v) ∈ Eb we create an edge (u0 , v0 ) of weight w(u, v).
– For every neutral edge (u, v) ∈ En we create edges (u0 , v0 ) and (u1 , v1 ) of weight
w(u, v).
We denote the weight function on the edges of the split graph by wsp . Vertices v0
will be called 0-vertices, and vertices v1 will be called 1-vertices.
We can naturally map Gsp to G by mapping the two vertices v0 and v1 to v for every
v ∈ V. We call the edges (up , vq ) ∈ E(Gsp ) the preimages of the edge (u, v) ∈ E for all
p, q ∈ {0, 1} for which such an edge is present in E(Gsp ).
Now we can state and prove the fundamental consequence of our construction.
Fact 7.9. Consider a cycle Csp in Gsp . If the image of Csp in G (obtained by contracting every
pair v0 , v1 of vertices into a single vertex v) crosses a tight set in L>2 , then it visits a vertex of
the backbone.
32

We remark that the image of a cycle in Gsp does not necessarily form a cycle in G
(as some vertices may be visited twice), but it is a subtour.
Proof. Consider a cycle Csp in Gsp whose image in G crosses a tight set in L>2 . In other
words, there is a set Si ∈ L>2 such that Csp ∩ δ({v0 , v1 : v ∈ Si }) , ∅. Let i∗ be the smallest
index of such a set. Then, by the choice of i∗ , an edge (uin , vin ) in the image of Csp
that enters Si∗ is a forward edge, and an edge (uout , vout ) in the image of Csp that exits
Si∗ is a backward edge. By the construction of Gsp , the single preimage of (uin , vin ) is
(u1in , v1in ) ∈ E(Gsp ), and the single preimage of (uout , vout ) is (u0out , v0out ) ∈ E(Gsp ). Thus
Csp must contain both (u1in , v1in ) and (u0out , v0out ). The statement now follows since the
only edges in Gsp from a 1-vertex to a 0-vertex are of the type (u1 , u0 ), where u ∈ V(B)
is a vertex of the backbone.

In order to work on the split graph, we will need to transform x into a circulation in
the split graph with similar guarantees as x. To do this, we take advantage of the fact
that every set S ∈ L>2 has a non-empty intersection with the vertices of the backbone.
Lemma 7.10. There is a polynomial-time algorithm that finds an Eulerian vector xsp ∈
E(Gsp )

such that the image of xsp in G is x, the optimal solution to LP(G, w). In particular,
P
0 1
e∈E(Gsp ) wsp (e)xsp (e) =
e∈E w(e)x(e) = value(I), and xsp (δ({v , v : v ∈ U})) = x(δ(U)) >
2 for each proper subset ∅ , U ( V.

R
P+

Proof. The main ingredient of the proof is the following claim.
Claim 7.11. In polynomial time, we can find a non-negative vector f ∈ RE+ satisfying:
(a) f 6 x,
(b) f (δ+ (v)) > f (δ− (v)) for every v ∈ V \ V(B),
(c) f (e) = 0 for each backward edge e ∈ Eb ,
(d) f (e) = x(e) for each forward edge e ∈ E f .
Intuitively, f resembles a flow supported on x that saturates all forward edges, does
not use backward edges, and has the backbone as a sink. Before we give the proof, let
us first motivate the existence of such an f in a simple example scenario where there is
only one non-singleton set S ∈ L>2 . Then we have E f = δ− (S) and Eb = δ+ (S), i.e., the
forward/backward edges are exactly the incoming/outgoing edges of S. The subtour
elimination constraints imply (via the min-cut max-flow theorem) that x supports a
unit flow between any pair of vertices. Let f be such a flow from any vertex outside
S to a vertex v ∈ S ∩ V(B) (such a v exists by the backbone property). It is easy to see
that f satisfies the conditions of the claim. Indeed, since S is a tight set, f saturates all
incoming (forward) edges. It also does not leave S, i.e., use any backward edges.
Now we proceed to give the full proof, which uses a more general argument based
on LP duality to argue the existence of f .

33

Proof of Claim 7.11. We find f ∈ RE+ in polynomial time by solving the following linear
program:
X
f (e)
maximize
e∈E f

subject to

f (δ+ (v)) > f (δ− (v)) for v ∈ V \ V(B),
f (e) = 0
for e ∈ Eb ,
0 6 f 6 x.

By the constraints of the linear program, we have that f satisfies (a), (b), and (c). It
remains to verify (d), or equivalently, to show that the optimum value of this program
equals x(E f ).
This will be shown using the dual linear program. The variables (πv )v∈V correspond
to the first set of constraints, and (z(e))e∈E f ∪En to the capacity constraints on forward
and neutral edges. No such variables are needed for backward edges. For notational
simplicity, we introduce πv also for v ∈ V(B), and set πv = 0 in this case. The dual
program can be written as follows.
X
x(e)z(e)
minimize
e∈E f ∪En

subject to

πv − πu + z(u, v) > 1 for (u, v) ∈ E f ,
πv − πu + z(u, v) > 0 for (u, v) ∈ En ,
πv = 0 for v ∈ V(B),
π, z > 0.

Note that setting π = 0, z(e) = 1 if e ∈ E f , and z(e) = 0 if e ∈ En is a feasible solution
with objective value x(E f ). We complete the proof by showing that this is an optimal
dual solution.
Let us select a dual optimal solution (π, z) which minimizes π(V). We show that
this minimum value is 0, that is, there exists a dual optimal solution with π = 0. This
immediately implies that the above solution is a dual optimal one, because given π = 0
we get a constraint z(u, v) > 1 for all (u, v) ∈ E f , making the objective value at least
x(E f ).
Towards a contradiction, assume that π is not everywhere zero. Let us select a
vertex t ∈ V such that πt > 0, and level(t) = i∗ is minimal among all such vertices. Let
S = Si∗ , and define T = {u ∈ S : πu > 0}. Since S ∩ V(B) , ∅, and πu = 0 for all u ∈ V(B),
we see that T is a proper subset of S. Let F = δ(V \ S, T) and F′ = δ(T, S \ T). A depiction
of the sets is as follows:
S = Si∗

F

T

F′

34

Let us show that the edges between T and S \ T can be only of certain types.
Claim. F′ = δ(T, S \ T) ⊆ E f ∪ En and δ(S \ T, T) ⊆ Eb ∪ En .
Proof of Claim. By the choice of i∗ , for any Si ( S we have that πv = 0 for all v ∈ Si ;
thus Si ∩ T = ∅, and so for every u ∈ T we have level(u) = i∗ . Therefore, for every
(u, v) ∈ F′ , we must have level(u) = i∗ > level(v), and for every (u, v) ∈ δ(S \ T, T),
level(v) = i∗ > level(u).
⋄
Let us construct another dual solution (π′ , z′ ) as follows. Let ε = min{πu : u ∈ T},
and let



z(e) + ε if e ∈ F ∩ (E f ∪ En ),





πu − ε if u ∈ T,

′
′
πu = 
and z (e) = 
z(e) − ε if e ∈ F′ ,


πu

otherwise,

z(e)
otherwise.

We show that (π′ , z′ ) is another optimal solution. Then, π′ (V) < π(V) gives a contradiction to the choice of (π, z). The proof proceeds in two steps: first we show feasibility
and then optimality.
Feasibility. We have π′ > 0 by the choice of ε. To show z′ > 0, note that for
e = (u, v) ∈ F′ , by the Claim and the dual constraints for e ∈ E f ∪ En we have 0 6
πv − πu + z(u, v) 6 z(u, v) − ε, where for the second inequality we used that πu > ε and
πv = 0. Thus, z(e) > ε and z′ (e) = z(e) − ε > 0 for every e ∈ F′ . For an edge e < F′ ,
we have z′ (e) > z(e) > 0 and so we can conclude that z′ > 0. We also have π′v = 0 for
v ∈ V(B) since T ∩ V(B) = ∅.
It remains to verify the constraints for (u, v) ∈ E f ∪ En . For every (u, v) ∈ (F ∪ F′ ) ∩
(E f ∪ En ), as well as for edges not in δ(T), we have π′v − π′u + z′ (u, v) = πv − πu + z(u, v),
and therefore the constraint remains valid. Thus we may have π′v − π′u + z′ (u, v) ,
πv −πu +z(u, v) in only two cases: either (i) if (u, v) ∈ δ(T, V \S), or (ii) if (u, v) ∈ δ(S\T, T).
In case (i), the constraint on (u, v) remains valid since π′v − π′u + z′ (u, v) = πv −
πu + z(u, v) + ε. In case (ii), π′u = 0, π′v > 0, and z′ (u, v) > 0. Further, we have shown
in the above Claim that (u, v) ∈ Eb ∪ En . There is no constraint for (u, v) ∈ Eb , and
π′v − π′u + z′ (u, v) > 0 holds if (u, v) ∈ En .
Optimality. When changing (π, z) to (π′ , z′ ), the objective value increases by ε(x(F ∩
(E f ∪ En )) − x(F′ ∩ (E f ∪ En ))) = ε(x(F \ Eb ) − x(F′ )); we will show that this is nonpositive. Recall that S is either a tight set or V, so that x(δ− (S)) 6 1. Since T ( S,
we have 1 6 x(δ− (S \ T)) = x(δ− (S)) − x(F) + x(F′ ) 6 1 − x(F) + x(F′ ), and therefore
x(F′ ) > x(F) > x(F \ Eb ). Thus, the objective value does not increase, therefore (π′ , z′ )
must be optimal.
The existence of the optimal solution (π′ , z′ ) with π′ (V) < π(V) contradicts the
⋄
choice of (π, z), which completes the proof of Claim 7.11.
Claim 7.11 implies Lemma 7.10 by defining xsp as follows:
– for every edge (u0 , v0 ) ∈ E(Gsp ), set xsp (u0 , v0 ) = x(u, v) − f (u, v),
– for every edge (u1 , v1 ) ∈ E(Gsp ), set xsp (u1 , v1 ) = f (u, v),
– for every v ∈ V, set xsp (v0 , v1 ) = max{0, f (δ+ (v)) − f (δ− (v))},
35

– for every v ∈ V(B), set xsp (v1 , v0 ) = max{0, f (δ− (v)) − f (δ+ (v))}.
By the properties of the above claim, it is easy to verify that xsp is a non-negative
Eulerian vector. It is also clear
P from this definition that for any e ∈ E, if P(e) denotes
the preimage set of e, then e′ ∈P(e) xsp (e) = x(e). This implies the statements on the
objective value and the cut values.

7.3.1

Proof of the Main Technical Lemma

We are ready to prove Lemma 7.3. We restate it here for convenience.
Lemma (restatement of 7.3). There is a polynomial-time algorithm that solves the following
problem. Let (I, B) be a vertebrate pair, and let U1 , . . . , Uℓ ⊆ V \ V(B) be disjoint non-empty
vertex sets such that the subgraphs G[U1 ], . . . , G[Uℓ ] are strongly connected and for every
S ∈ L>2 and i = 1, . . . , ℓ we have either Ui ∩ S = ∅ or Ui ⊆ S. Then the algorithm finds an
Eulerian multiset F ⊆ E of edges such that:
(a) w(F) 6 3 · value(I),
(b) |δ−F (Ui )| > 1 for every i = 1, . . . , ℓ,
(c) |δ−F (v)| 6 4 for every v ∈ V with x(δ− (v)) = 1,
(d) any subtour in F that crosses a tight set in L>2 visits a vertex of the backbone.
The proof proceeds in two steps. In the first step, we further modify Gsp and xsp to
and x′sp , by taking the sets Ui into account. In the second step, we obtain the set F
by solving a minimum-weight integral circulation problem on G′sp .

G′sp

Modifying the split graph. The graph G′sp is constructed as follows (see also Figure 8).
sp
For i = 1, . . . , ℓ let Ui = {v0 , v1 : v ∈ Ui } ⊆ V(Gsp ) be the set of vertices in the split
graph corresponding to Ui . We select edge sets Xi− , Xi+ , and a flow 1i as follows:
sp

– Select a subset of edges Xi− ⊆ δ− (Ui ) with xsp (Xi− ) = 1/2 such that either all
edges in Xi− enter 1-vertices, or all of them enter 0-vertices. This is possible since
sp
xsp (δ− (Ui )) > 1 by Lemma 7.10.11
sp

– Define the set of outgoing edges Xi+ ⊆ δ+ (Ui ) to be, intuitively, the edges over
sp
sp
which the flow that entered Ui by Xi− exits Ui . That is, consider an arbitrary
cycle decomposition of the circulation xsp , and look at the set of cycles containing
the edges in Xi− . We define Xi+ as the set of edges on these cycles that first leave
sp
sp
Ui after entering Ui on an edge in Xi− ; clearly, xsp (Xi+ ) = 1/2.12
– Let 1i denote the flow on these cycle fragments connecting the heads of edges in
Xi− and the tails of edges in Xi+ .
11

To obtain exactly 1/2, we might need to break an edge up into two copies, dividing its xsp -value
between them appropriately, and include one copy in Xi− but not the other; we omit this for simplicity of
notation, and assume there is such an edge set with exactly xsp (Xi− ) = 1/2.
12
Again, we might need to split some edges into two copies.

36

1/8

2/3

1/8

2/3

1/6

1/4

11/12

1/4

1/8

1/4

1/6

2/3

2/3
1/4

1/3
1/3

1/4

2/3

ai

1/6
1/4

1/8

1/6

1/2

1/4

1/3
1/3

1/2

1/4

Figure 8: An example of the modification of the split graph. Squares and circles are 1and 0-vertices, respectively.
sp
On the left, a single set Ui is depicted. We only draw the edges that are part
sp
of those cycles in the decomposition of xsp that enter and exit Ui . The thick
sp
edges are Xi− and Xi+ , and the solid edges inside Ui are those that carry 1/4
flow in 1i .
On the right, we show the corresponding part of the modified split graph
G′sp and the modified circulation x′sp obtained by redirecting the edges in Xi−
and Xi+ to a new auxiliary vertex ai and by subtracting the flow 1i .
We now transform Gsp into a new graph G′sp and xsp into a new Eulerian vector x′sp .
For every i = 1, . . . , ℓ, we introduce a new auxiliary vertex ai and redirect all edges in Xi−
sp
to point to ai , and those in Xi+ to point from ai . We further subtract the flow 1i inside Ui ;
hence the resulting vector x′sp will be Eulerian in G′sp , with x′sp (δ− (ai )) = x′sp (δ+ (ai )) = 1/2.
We define the weights w′sp (e) = wsp (e) if e was not modified, and for every redirected
edge e we set w′sp (e) as the weight
of the edge it was
P
P redirected from. Thus, the total
′
′
weight may only decrease: e∈E(G′sp ) wsp (e)xsp (e) 6 e∈E(Gsp ) wsp (e)xsp (e) = value(I) (it
decreases if the flows 1i are nonzero on edges with positive weight).
Solving the circulation problem. Having defined the modified split graph G′sp and
the circulation x′sp , we now describe how to use them to find F.
Claim. One can find, in polynomial time, an integral circulation (i.e., an Eulerian vector)
z′sp in G′sp satisfying:

 l

m
– z′sp δ− (v0 ) \ {(v1 , v0 )} 6 2x′sp δ− (v0 ) \ {(v1 , v0 )} for each v0 ∈ V(G′sp ),

 l

m
– z′sp δ− (v1 ) \ {(v0 , v1 )} 6 2x′sp δ− (v1 ) \ {(v0 , v1 )} for each v1 ∈ V(G′sp ),
– z′sp (δ− (ai )) = 1 for each i = 1, . . . , ℓ,
P
– e∈E(G′sp ) w′sp (e)z′sp (e) 6 2 · value(I).

37

Proof of Claim. The well-known integrality of the circulation polyhedron asserts that,
given integer upper and lower capacity bounds on the edges, if there is a feasible
circulation, then for any weight function there is a minimum-weight integer circulation
(see e.g. Corollary 12.2a in [Sch03]). We wish to use this theorem by transforming the
above conditions into edge capacity bounds. We do so by introducing further auxiliary
edges.
The reduction is as follows. For the first set of constraints, we split v0 further into
v0 and v̄0 , add an edge (v̄0 , v0 ), and replace all incoming edges (z, v0 ) ∈ E(G′sp ) for
z , v1 by (z, v̄0 ). In that way, constraints from the first set become capacity constraints
on the new edges (v̄0 , v0 ) (which are integral because we take the ceiling). A similar
construction is used for the second set of constraints. Finally, for the node capacity
constraint on ai , we add a new āi with an edge (āi , ai ), and redirect all incoming edges in
δ− (ai ) to point to āi . We add upper and lower bounds on these new edges as required.
Note that the fractional circulation 2x′sp satisfies all the conditions in the claim; its
natural image under these transformations will satisfy all edge capacity constraints.
Hence we can find a minimum-weight integral circulation in the modified graph,
which naturally maps back to an integral circulation z′sp in G′sp whose weight is at most
⋄
that of 2x′sp , i.e., at most 2 value(I).
We then let Fsp ⊆ E(Gsp ) be the multiset of edges of the (unmodified) split graph
obtained by, for each e ∈ E(G′sp ), taking z′sp (e) copies of the corresponding edge in Gsp ,
i.e., if e is incident to an auxiliary vertex ai , then reverse the redirection
of this edge
P
so as to obtain its preimage in Gsp . We thus have wsp (Fsp ) = e∈E(G′sp ) w′sp (e)z′sp (e) 6
2 · value(I).
We remark that Fsp may not be Eulerian. Specifically, since the in- and out-degree
p q
of ai were exactly 1 in z′sp , in each component Ui there is a pair of vertices ui , vi which
are the head and tail, respectively, of the mapped-back edges adjacent to ai . These
are the only vertices whose in-degree may differ from their out-degree. (They differ
q
p
unless ui = vi .) As the third step, to repair this, for each i = 1, . . . , ℓ we route a walk Pi
q
p
from ui to vi in Gsp . The walk Pi is selected as follows:
– Let ui , w1 , . . . , wt , vi be a shortest path in G from ui to vi inside Ui , which exists
since G[Ui ] is assumed to be strongly connected.
– By the assumption on Ui (that it is either contained in or disjoint from any set
in L>2 ), all edges in G[Ui ] cross no set in L>2 , i.e., are neutral edges. Hence the
p
p
p p
path P̄i = ui , w1 , . . . , wt , vi is present in Gsp .
– If p = q, then we define Pi = P̄i . If p = 0 and q = 1, then we define Pi by appending
the edge (v0i , v1i ) to P̄i ; note that this edge is always included in E(Gsp ). Finally,
the next claim shows that p = 1, q = 0 is not possible.
Claim. If the head of an edge in Xi− is a 1-vertex, then the tail of every edge in Xi+ is a
1-vertex.
Proof of Claim. By the way that Xi− was defined, all edges in Xi− enter 1-vertices if at
least one does. Further, the only edges from 1-vertices to 0-vertices in Gsp are of the
38

type (v1 , v0 ) where v ∈ V(B), and it is assumed that Ui ∩ V(B) = ∅. Therefore, any flow
sp
sp
that enters Ui on a 1-vertex only visits 1-vertices until it exits Ui .
⋄
The Eulerian multiset F ⊆ E of edges in G is now obtained from the Eulerian set
0 1
i=1 Pi ∪ Fsp of edges in Gsp by contracting every pair v , v into a single vertex v. This
completes the description of the algorithm for finding F.
The computation of F can be done in polynomial time as it is based on solving a
minimum-weight circulation problem on G′sp , together with basic graph operations. It
remains to verify properties (a) - (d) of the lemma.
For (a), we use that the path Pi has the same weight as a shortest path in G[Ui ]
from a vertex ui ∈ Ui to a vertex vi ∈ Ui . Since Ui is either disjoint from or contained in
any tight setPin L>2 , every edge (u, v) inside Ui has weight yu + yv and thus we have
w(Pi ) 6 2 · v∈Ui yv 6 value(Ui ). The overall weight of F is the weight of the edges
corresponding to z′sp plus the weight of the paths. Hence
Sℓ

w(F) 6 2 · value(I) +

ℓ
X

value(Ui ) 6 3 · value(I)

i=1

by disjointness of the sets Ui .
Now consider property (b). For each i = 1, . . . , ℓ there is an edge e ∈ F corresponding
to (i.e., is the preimage of) the incoming edge e′ of the auxiliary vertex ai with z′sp (e′ ) = 1.
By construction, the edge e′ corresponds to an edge e′′ in Gsp such that e′′ ∈ Xi− ⊆
sp
δ− (Ui ) and thus e ∈ δ− (Ui ). So (b) holds.
For property (c), first notice that path Pi was formed from a shortest path that was
sp
completely contained in Ui , and since the sets Ui (and thus Ui ) are disjoint, the degree
in F of any vertex v is at most one more than the degree of {v0 , v1 } in the circulation z′sp .
Thus
|δ−F (v)| 6 z′sp (δ− ({v0 , v1 })) + 1




= z′sp δ− (v0 ) \ {(v1 , v0 )} + z′sp δ− (v1 ) \ {(v0 , v1 )} + 1
l

m l

m
6 2x′sp δ− (v0 ) \ {(v1 , v0 )} + 2x′sp δ− (v1 ) \ {(v0 , v1 )} + 1 .

Assume now that x(δ− (v)) = 1. We have

x(δ− (v)) = xsp (δ− ({v0 , v1 }))
> x′sp (δ− ({v0 , v1 }))




= x′sp δ− (v0 ) \ {(v1 , v0 )} + x′sp δ− (v1 ) \ {(v0 , v1 )} ,
   
where the first equality is by Lemma 7.10. Thus we have to bound 2p + 2q + 1
subject to p + q 6 1. Clearly, the maximum is 4, and (c) follows.
Finally, property (d) immediately follows from Fact 7.9. Indeed, F was obtained
from an Eulerian edge set in the split graph Gsp by contracting every pair v0 , v1 into
a single vertex v. In other words, F is the image of an Eulerian multiset of edges in
the split graph Gsp . As any Eulerian multiset can be be decomposed into cycles, this
is equivalent to saying that F is the union of images of cycles in Gsp . Fact 7.9 says that
any such image that crosses a tight set in L>2 must visit a vertex in the backbone.
This concludes the proof of Lemma 7.3.
39

8 Completing the Puzzle: Proof of Theorem 1.1
We now combine the techniques and algorithms of the previous sections to obtain a
constant-factor approximation algorithm for ATSP. In multiple steps, we have reduced
ATSP to finding tours for vertebrate pairs. Every reduction step was polynomial-time
and increased the approximation ratio by a constant factor. Hence, together they give
a constant-factor approximation algorithm for ATSP.
We now give an overview of these reductions and set the parameters. Throughout,
ε > 0 will be a fixed small value. We set δ = 0.75. All approximation guarantees are
with respect to the optimum value of the Held-Karp relaxation LP(G, w). The reduction
proceeds using the following algorithmic subroutines.
– Algorithm ANW from [Sve15], which is a polynomial time αNW -approximation
for node-weighted ATSP, with αNW = 27 + ε (Theorem 2.2). This will be used to
find a (quasi-)backbone for irreducible instances (Lemma 6.3).
– Algorithm Aver , which, for a vertebrate pair (I, B), finds a tour of cost κ value(I)+
ηw(B), where κ = 8(9 + ε) and η = (9 + ε) (Theorem 7.1). Algorithm Aver uses the
reduction Theorem 7.2 from Local-Connectivity ATSP to ATSP (see [Sve15]). For
Local-Connectivity ATSP, we use the 8 + w(B)/value(I)-light algorithm of Section 7.2.
– Algorithm Airr which, provided Aver as above, obtains a polynomial-time ρapproximation algorithm for irreducible instances, where ρ = (κ + η(αNW +
3))/(1 − 2(1 − δ)) = 684 + ε′ (Theorem 6.4).
– Algorithm Alam , which converts the ρ-approximation algorithm Airr to a
2ρ/(1−δ)-approximation algorithm for an arbitrary laminarly-weighted instance
I. Here, 2ρ/(1 − δ) = 5472 + ε′′ < 5500 (Theorem 5.3).
– Our final Algorithm AATSP , which reduces an arbitrary input weighted digraph
(G, w) to a laminarly-weighted instance, keeping the same approximation ratio
(Theorem 2.4).
All in all we have thus obtained a polynomial-time algorithm for ATSP that returns
a tour of value at most a constant (5500) times the Held-Karp lower bound.

9 Conclusion
In this paper we gave the first constant-factor approximation algorithm for ATSP. The
result was obtained in two steps. First, we gave a generic reduction to ATSP instances
with a backbone, i.e., vertebrate pairs. These instances were then solved using the
connection to Local-Connectivity ATSP introduced in [Sve15]. We believe that, by
specializing and optimizing the techniques of [Sve15] to the setting of this paper, the
integrality gap of the LP relaxation can be upper-bounded by the hundreds. However,
achieving an upper bound on the integrality gap that is close to the current lower
bound of 2, even say an upper bound of 50, seems to require substantial progress. We
raise this as an important open problem.
40

Open Question 9.1. Is the integrality gap of the standard LP relaxation upper-bounded
by 2?
As mentioned in the introduction, Asadpour et al. [AGM+ 10] introduced a different approach for ATSP based on so-called thin spanning trees. Our algorithm does not
imply a better construction of such trees and the O(poly log log n)-thin trees of [AG15]
remain the best such (non-constructive) result. Whether trees of better thinness exist
is an interesting question. Also, as shown in [AKS10], the construction of O(1)-thin
trees would lead to a constant-factor approximation algorithm for the bottleneck ATSP
problem. There, we are given a complete digraph with edge weights satisfying the
triangle inequality, and we wish to find a Hamiltonian cycle that minimizes the maximum edge weight. A tight 2-approximation algorithm for bottleneck symmetric TSP
was given already in [Fle74, Lau81, PR84], but no constant-factor approximation is
known for bottleneck ATSP.
Open Question 9.2. Is there a O(1)-approximation algorithm for bottleneck ATSP?
We believe that this is an interesting open question in itself, and progress on it may
shed light on the existence of O(1)-thin trees.

References
[AG15]

Nima Anari and Shayan Oveis Gharan. Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 20–39, 2015. 2, 41

[AGM+ 10] Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan,
and Amin Saberi. An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010, pages 379–389, 2010. 2, 41
[AKS10]

Hyung-Chan An, Robert D. Kleinberg, and David B. Shmoys. Approximation
algorithms for the bottleneck asymmetric traveling salesman problem. In APPROX,
pages 1–11, 2010. 41

[AKS15]

Hyung-Chan An, Robert D. Kleinberg, and David B. Shmoys. Improving
Christofides’ algorithm for the s-t path TSP. J. ACM, 62(5):34:1–34:28, 2015. 10

[Blä08]

Markus Bläser. A new approximation algorithm for the asymmetric TSP with
triangle inequality. ACM Transactions on Algorithms, 4(4), 2008. 2

[CFN85]

Gérard Cornuéjols, Jean Fonlupt, and Denis Naddef. The traveling salesman
problem on a graph and some related integer polyhedra. Mathematical Programming,
33(1):1–27, 1985. 7

[CGK06]

Moses Charikar, Michel X. Goemans, and Howard J. Karloff. On the integrality
ratio for the asymmetric traveling salesman problem. Math. Oper. Res., 31(2):245–
252, 2006. 2, 3

[Chr76]

Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Graduate School of Industrial Administration,
CMU, 1976. 2

41

[FGM82]

Alan M. Frieze, Giulia Galbiati, and Francesco Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12(1):23–39, 1982. 2

[Fle74]

Herbert Fleischner. The square of every two-connected graph is Hamiltonian.
Journal of Combinatorial Theory, Series B, 16(1):29 – 34, 1974. 41

[FS07]

Uriel Feige and Mohit Singh. Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop,
APPROX 2007, and 11th International Workshop, RANDOM 2007, pages 104–118,
2007. 2

[GS11]

Shayan Oveis Gharan and Amin Saberi. The asymmetric traveling salesman problem on graphs with bounded genus. In Proceedings of the Twenty-Second Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pages 967–975, 2011. 2

[GSS11]

Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding
approach to the traveling salesman problem. In IEEE 52nd Annual Symposium on
Foundations of Computer Science, FOCS 2011, pages 550–559, 2011. 2

[Kar96]

Alexander Karzanov. How to tidy up a symmmetric set-system by use of uncrossing operations. Theoretical Computer Science, 157:215–225, 1996. 7

[KLS13]

Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability
bounds for TSP. In Algorithms and Computation - 24th International Symposium,
ISAAC 2013, pages 568–578, 2013. 3

[KLSS05]

Haim Kaplan, Moshe Lewenstein, Nira Shafrir, and Maxim Sviridenko. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM, 52(4):602–626, 2005. 2

[Lau81]

H. T. Lau. Finding EPS-graphs. Monatshefte für Mathematik, 92(1):37–40, Mar 1981.
41

[MS16]

Tobias Mömke and Ola Svensson. Removing and adding edges for the traveling
salesman problem. J. ACM, 63(1):2:1–2:28, 2016. 2

[Muc12]

Marcin Mucha. 13/9-approximation for graphic TSP. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, pages 30–41, 2012.
2

[PR84]

R.Gary Parker and Ronald L Rardin. Guaranteed performance heuristics for the
bottleneck travelling salesman problem. Operations Research Letters, 2(6):269 – 272,
1984. 41

[Sch03]

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer,
2003. 38

[STV16]

Ola Svensson, Jakub Tarnawski, and László A. Végh. Constant factor approximation for ATSP with two edge weights. In IPCO, pages 226–237, 2016. 3, 4,
27

[SV14]

András Sebő and Jens Vygen. Shorter tours by nicer ears: 7/5-approximation for
the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs.
Combinatorica, 34(5):597–629, 2014. 2

[Sve15]

Ola Svensson. Approximating ATSP by relaxing connectivity. In FOCS 2015:
Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science,
2015. 2, 3, 4, 7, 26, 27, 40

42

