Approximability of TSP on Power Law
Graphs
Mikael Gast∗

Mathias Hauptmann†

Marek Karpinski‡

arXiv:1509.03976v1 [] 14 Sep 2015

Abstract
In this paper we study the special case of Graphic TSP where the underlying
graph is a power law graph (PLG). We give a refined analysis of some of the current
best approximation algorithms and show that an improved approximation ratio
can be achieved for certain ranges of the power law exponent β. For the value of
power law exponent β = 1.5 we obtain an approximation ratio of 1.34 for Graphic
TSP. Moreover we study the (1, 2)-TSP with the underlying graph of 1-edges being
a PLG. We show improved approximation ratios in the case of underlying deterministic PLGs for β greater than 1.666. For underlying random PLGs we further
improve the analysis and show even better expected approximation ratio for the
range of β between 1 and 3.5. On the other hand we prove the first explicit inapproximability bounds for (1, 2)-TSP for an underlying power law graph.

1

Introduction

Given a set of cities along with the distance between each pair of them, the Traveling
Salesman Problem (TSP) is to find the shortest tour through all the cities and returning
to the starting point. The TSP is one of the best known problems in combinatorial
optimization and has many applications, for example in the fields of logistics, genetics
and telecommunications. It is well known that the general TSP is N P -hard [Kar72] and
that, unless P = N P , there can be no efficient approximation algorithm for the TSP
that achieves some bounded approximation ratio [SG76]. For the case of the (symmetric)
Metric TSP with a distance function satisfying the triangle inequality Christofides devised
a 3/2-approximation algorithm [Chr76] which has seen no improvement for nearly four
decades. But a number of improvements were made for some special cases of Metric TSP
(see e.g. [BK06; SV14]). We refer to [AT15] and [Kar15] for an overview of some of the
current approximability and inapproximability results.
In this paper we study two special cases of Metric TSP, namely, the (1, 2)-TSP with
distances between cities being either one or two, and the Graphic TSP where we assume
∗

Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn. e-mail:
gast@cs.uni-bonn.de
†
Dept. of Computer Science, University of Bonn. e-mail: hauptman@cs.uni-bonn.de
‡
Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn. Research
supported by DFG grants and the Hausdorff grant EXC59-1. e-mail: marek@cs.uni-bonn.de

1

that the metric is the shortest path metric of an undirected graph. More precisely we are
interested in the case of Graphic TSP where the underlying graph is a power law graph,
and, for the (1, 2)-TSP, where the undirected graph of 1-edges is a power law graph.
Power law graphs have the property that their node degree distribution follows a
power law, i.e. the number of nodes of degree i is proportional to i−β , for some fixed
power law exponent β > 0. This parameter β is called the power law exponent. Many of
the existing real-world networks turn out to be power law graphs. This has been observed
for the graphs of the Internet and the World Wide Web (WWW), peer-to-peer networks,
gene regulatory networks and protein interaction networks and for social networks.
Our Results In this paper we study the special case of the Graphic TSP when the
underlying graph is a power law graph. We denote the special case as Power Law Graphic
TSP. For the case when the power law exponent β satisfies 1 < β < 2.48 and the graph
ζ(β)
, where
is connected, we show that the problem is approximable within 21 + max{2,ζ(β)+1/2}
P∞ −β
ζ(β) = i=1 i is the Riemann Zeta Function. For β > 1.256, this improves over the
current best Graphic TSP upper approximation bound of 7/5 due to [SV14]. In particular,
for β = 1.5 this yields an approximation ratio of 1.339. For β = 2.5, the resulting
approximation ratio is 1.171. For β > 2.479, power law graphs are not connected any
more.
Then we consider the (1, 2)-TSP with underlying power law graph, which we denote
as Power Law (1, 2)-TSP. For the case β > 1, we obtain an approximation ratio of
11
29
2ζ(β)+ 21 ζ(β−1)−1
ζ(β)+ 72
9
.
For
β
>
2.729
we
obtain
an
improved
ratio
of
which converges
1
ζ(β)+ 2
ζ(β)+ 12
to 1 as β → ∞. For β > 1.666, this improves over the current best (1, 2)-TSP upper
approximation bound of 8/7 due to [BK06]. For β = 1.5, this yields a 1.155-approximation
and for β = 2.5 a 1.109-approximation.
In the case when the underlying graph is a random PLG with β > 1, we obtain an
improved expected approximation ratio. In the case 1 < β < 2 and β = 2 this is equal
11
11
ζ(β)+ 29 · 54
ζ(β)+ 29 · 85
and 9 ζ(β)+36
, respectively. For β > 2 the expected approximation ratio
to 9 ζ(β)+36
5
5
11

4

ζ(β)+ 29 ·E

8

k
36
is 9 ζ(β)+E
, where Ek is the expected lower bound on the number of 2-edges in an
k
optimum tour.
On the other hand we show that for β > 1, the Power Law (1, 2)-TSP is NP-hard to
1/2)·3β−1 ·2·(β−1)·354+1
approximate within approximation ratio (ζ(β)+
. This gives an approxi(ζ(β)+1/2)·3β−1 ·2·(β−1)·354
mation lower bound of 1.00086 for β = 1.2 and of 1.0012 for β = 1.1.

Organization of the Paper In Section 2 we give an outline of the methods and
constructions used in the paper. Section 3 provides the definition of the PLG model due
to [ACL01] and related notations. In Section 4 we describe our results for the Graphic
TSP on power law graphs. In Section 5 we present our results on the (1, 2)-TSP with
underlying power law graph. Section 5.1 contains the analysis of the algorithm from
[PY93] for deterministic power law graphs. Section 5.2 deals with the case of a large
power law exponent. In Section 5.3 we consider the case when the underlying graph is a
random PLG. Approximation lower bounds are given in Section 5.4.

2

2

The Method

We give first a brief outline of the methods and constructions used in this paper. For
the Graphic TSP with underlying power law graph, we give an improved analysis of the
algorithms of Christofides [Chr76], Mömke-Svensson [MS11] and the algorithm of Mucha
[Muc12]. This is based on the analysis of local configurations in PLGs, consisting of a
high-degree node and its degree 1 and 2 neighbors. We show that any such configuration
contributes to the lower bound for the length of an optimum tour. The same idea also
applies to the (1, 2)-TSP with underlying PLG.
The approximation hardness results for the (1, 2)-TSP with underlying PLG are based
on efficient embeddings of graphs into power law graphs. We start from the lower bound
for (1, 2)-TSP given in [KLS13]. We map the associated graphs to instances which contain
a perfect matching. This is then used in order to embed those graphs into sufficiently
small PLGs.

3

Preliminaries

In this section we first give the formal definition of (α, β)-power law graphs. Then we
provide estimates for sizes and volumes of some subsets of the vertex set of a power law
graph which we call intervals. Later on we make use of these estimates in the analysis of
our upper and lower bound constructions.
Definition 3.1. [ACL01] An undirected multigraph G = (V, E) with self loops is called
an (α, β) power law graph if the following conditions hold:
• The maximum degree is ∆ = beα/β c.
• For i = 1, . . . , ∆, the number yi of nodes of degree i in G satisfies
yi =

 α
e

iβ

The following estimates for the number n of vertices of an (α, β) power law graph are
well known [ACL01]:
n≈


eα/β


 1−β




α

α·e
ζ(β) · eα

for 0 < β < 1,
for β = 1,
for β > 1.

m≈


1 e2α/β


 2 2−β




1
αeα
4
1
ζ(β −
2

1)eα

for 0 < β < 2,
for β = 2,
for β > 2.

−β
Here ζ(β) = ∞
is the Riemann Zeta Function.
i=1 i
By P (α, β) we denote the probability distribution on the set Gα,β which is obtained
in the following way [ACL01]:

P

1. Generate a set L of d(v) distinct copies of each vertex v.
2. Generate a random matching on the elements of L.
3. For each pair of vertices u and v, the number of edges joining u and v in Gα,β is
equal to the number of edges in the matching of L, which join copies of u to copies
of v.
3

d(v) = 1

d(v) = 2

d(v) = 3

V
...

...

...

...

L
edge

self-loop

multi-edge
Figure 1:

As in [ACL01], in the following we work with the real numbers eiβ , e β instead of their
α
integer counterparts. For β > 2 the overall error is bounded by e β = o(n) (c.f. [ACL01],
remark on page 6).
Given an (α, β) power law graph G = (V, E) with n vertices and maximum degree ∆
and two integers 1 6 a 6 b 6 ∆, an interval [a, b] is defined as the subset of V
α

α

[a, b] = {v ∈ V |a 6 degG (v) 6 b}
If U ⊆ V is a subset of vertices, the volume vol(U ) of U is defined as the sum of node
degrees of nodes in U . In Section 4 we will make use of estimates of sizes and volumes
of node intervals in (α, β)-PLGs. In particular we will show that in the case β > 2 the
volume of a node degree interval of the form [x∆, ∆] = {v|x∆ 6 deg(v) 6 ∆} is bounded
e2α/β
by (β−2)x
β−2 .

4

Graphic TSP on Power Law Graphs

In this section we consider the Graphic TSP in power law graphs. Given a connected
graph G = (V, E) with n vertices, the Graphic TSP asks for a minimum cost tour on the
vertices with respect to the shortest path metric induced by G. This is a natural special
case of the general TSP and it was shown that an improvement of the approximation
algorithm of Christofides’ algorithm can be achieved. The first small improvement is due
to Gharan, Saberi, and Singh [GSS11] who showed a ( 23 − ε)-approximation (for an ε
in the order of 10−12 ) based on a refined analysis of Christofides’ algorithm for Graphic
instances. A whole different approach is due to Mömke and Svensson [MS11] where the
starting point is a 2-vertex connected graph which√is made Eulerian by removing edges.
√ 2−1) < 1.461 which was subsequently
This approach yields an approximation ratio of 14(
12 2−13
improved by Mucha [Muc12] to a ratio of 13
≈ 1.444. The current best approximation
9
7
ratio of 5 is achieved by Sebő and Vygen [SV14].
Here we consider the special case of Graphic TSP when the underlying graph G is an
(α, β)-PLG. We show that—for certain ranges of the parameter β—a refined analysis of
the above algorithms yield better approximation ratios in this case. Our results hold for
1 < β < 2.479, namely when ζ(β − 1) > 2 · ζ(β). For ζ(β − 1) 6 2 · ζ(β), (α, β)-PLGs
are not connected anymore.
4

4.1

Improved Analysis

We start by slightly improving the analysis of the basic 2-approximation algorithm for
TSP applied on instances of Graphic TSP with an underlying (α, β)-PLG. For the general
TSP instances, a 2-approximation can easily be achieved by the so called MST heuristic.
In order to construct a tour one computes a minimum spanning tree (MST) of G and
replaces each edge of the tree by a pair of parallel edges. The resulting multigraph is
Eulerian, and making use of triangle inequality, an Euler tour can be transformed into a
traveling salesman tour. Since any tour is connected and thus contains a spanning tree, a
MST has cost at most half of the optimum tour. For the case of an underlying (α, β)-PLG
α
the cost of an MST is ζ(β)eα − 1, while every tour has cost at least ζ(β)eα + e2 . This
lower bound holds since G contains eα nodes of degree 1. As we shall see below in the
analysis of Christofides’ algorithm on PLGs, we also have c(τ ) > 2eα for every tour τ .
Thus we obtain the following result.
Lemma 1. For 1 < β < 2.48, the approximation ratio of the MST heuristic for (α, β)2ζ(β)
Power Law Graphic TSP is bounded by max{2,ζ(β)+
1 .
}
2

Now we consider the performance of Christofides’ algorithm [Chr76] on power law
Graphic instances. On general instances, this algorithm constructs an MST T and a
minimum cost perfect matching M on the subset of nodes which have an odd degree in
T . If τ ∗ denotes an optimum TSP tour, then c(M ) 6 c(τ ∗ ) and c(M ) 6 c(τ ∗ )/2, which
yields the approximation ratio of 1.5 for the general Metric TSP. Now we will improve
this bound for the special case of (α, β)-Power Law Graphic TSP when β > 1. Again
the MST cost is c(T ) = ζ(β)eα − 1 6 c(τ ∗ ). The problem now is that we do not know in
advance if the matching cost c(M ) is close to c(T ) or close to 21 c(T ).
Our approach is to charge at least some part of the matching cost in order to get an
improved approximation ratio. First we observe that all degree 1 nodes in G have an odd
degree in T . Thus we obtain that
c(τ ∗ )
− eα ,
c(M ) = e + (c(M ) − e ) 6 e +
2
!

α

α

α

from which we also conclude that c(τ ∗ ) > 2eα . Moreover, c(τ ∗ ) > (ζ(β) + 21 )eα . Hence
the approximation ratio is bounded by
∗)

ζ(β)eα + c(τ2
ζ(β)eα + c(M )
6
c(τ ∗ )
c(τ ∗ )

6

1
ζ(β)
+
2 max{2, ζ(β) + 12 }

We have shown the following result.
Lemma 2. For 1 < β < 2.48, the approximation ratio of Christofides’ algorithm on
ζ(β)
(α, β)-power law Graphic instances is at most 21 + max{2,ζ(β)+
1 .
}
2

Now we consider the Mömke-Svensson algorithm for TSP [MS11]. It is based on the
notion of removable pairings. A removable pairing (R, P) consists of a subset of edges
R ⊆ E and a subset P ⊆ P (E) of the power set of E such that P = {Pv |v ∈ U } for some
subset U ⊆ V , each v ∈ U has degree at least 3 and Pv is a set of two edges incident
5

to v. The sets in P have to be pairwise disjoint. Moreover, for each subset F ⊆ R such
that for each v ∈ U , F contains at most one element from Pv , the graph (V, E \ F ) is
connected.
Mömke and Svensson [MS11] show that, given a removable pairing (R, P), one can
construct in polynomial time a tour τ of cost c(τ ) 6 43 c(E) − 32 c(R). This yields an
approximation ratio of 43 for Subcubic Graphic TSP, i.e. Graphic TSP in graphs of
maximum degree at most 3. We now analyse the performance of this algorithm for Power
Law Graphic TSP for β > 2. Note that for β 6 2 the Mömke-Svensson bound is not
applicable, since the cardinality of E is not linear in |V | anymore. In the case β > 2,
we use our lower bound c(τ ∗ ) > max{2, ζ(β) + 12 } · eα . We apply the Mömke-Svensson
algorithm to every 2-vertex connected component of the graph G = (V, E). Suppose first
that the subgraph G0 = (V 0 , E 0 ) induced by the vertices of degree at least 2 is 2-vertex
connected. Now we have to give a bound on the size of the set R, where (R, P) is a
removable pairing used in the algorithm. This is constructed as follows. Choose a root
v ∈ V and let (V, S) be a DFS tree in G0 rooted at r. Initially, R : = E \ S and P = ∅.
Then the vertices v ∈ V are processed in any order. For each such v, if v has degree at
least 3, is incident to some edge e = {v, w} ∈ E \ S such that v is on the r − w−path in
(V, S), e0 is the first edge on the subpath from v to w and e0 has not yet been added to
R, then add e0 to R and {e, e0 } to the set P.
First we observe that in the case β > 2,
|E 0 \ S| > |E| − |{v|deg(v) = 1}| − (|V 0 | − 1)


1
1
α
α
α
ζ(β − 1) − ζ(β) eα
> ζ(β − 1)e − e − (ζ(β) − 1)e =
2
2
Given an edge e ∈ E 0 \ S with e = {v, w} such that v lies on the r − w−path in the DFS
tree, then v is called the root of the edge e. Since each such root gives rise to at least
one additional edge in the set R, we will now give a lower bound on the number of roots
needed to cover all the edges in E 0 \ S. Each root v ∈ V 0 \ {r} has degree at least 2 plus
the number of edges e ∈ E 0 \ S with root v.
The volume of a set of nodes is defined as the sum of their node degrees. In Power
Law Graphs, in the case β > 2 the volume of a node degree interval [x∆, ∆] = {v|x∆ 6
deg(v) 6 ∆} can be estimated as follows:
vol([x∆, ∆]) =

∆  α
X
e
i=x∆

iβ

·i6

= (1 + o(1))e

α

"

∆
X

eα

i=xδ

iβ−1

2−β

#∆+1

y
2−β

∆+1
Z

α

x∆

6e

x∆

e
e2α/β
=
(β − 2) · xβ−2
(β − 2)xβ−2

The volume available for edges e ∈ E 0 \ S is
∆  α
X
e
i=x∆

iβ

(i − 2) 6

e2α/β
− 2(1 − x)∆
(β − 2)xβ−2
6

xβ−1

dx + (1 − x)∆

(1 + o(1)) eα
=
β−2

α−α· β−2
β

6

1

1
1
−
β−2
(x∆)
(∆ + 1)β−2

!

Now this volume has to cover the set E 0 \ S, i.e.
e2α/β
1
ζ(β − 1) − ζ(β) eα
− 2(1 − x)∆ >
β−2
(β − 2)x
2
which holds if and only if


e2α/β
1
ζ(β − 1) − ζ(β) eα
> (1 + o(1)) ·
β−2
(β − 2)x
2




Hence we have to choose
x6

e−α/β
((β − 2)( 12 ζ(β − 1) − ζ(β)))1/(β−2)

Then the size of the set [x∆, ∆] is
∆  α
X
e
x∆

iβ

> eα ·

(x∆)1−β − (∆ + 1)1−β
−∆
β−1

eα
1
> (1 − o(1))
· (β − 2) ζ(β − 1) − ζ(β)
(β − 1)
2


 β−1



β−2

Thus we obtain an improved lower bound on the size of the set R as follows:
|R| > |E \ S|
α [(β

+ (1 − o(1))e

β−1

− 2)(ζ(β − 1)/2 − ζ(β) + 1] β−2
β−1
β−1
β−2

We let tβ := eα [(β−2)(ζ(β−1)/2−ζ(β)+1]
. We obtain that the cost of the tour τ constructed
β−1
by the Mömke-Svensson algorithm is bounded as
2
4
c(τ ) 6 |E| − |R|
3
3
2
2
2
6 |E| + |S| − tβ eα
3
3
3


2
2
5 α
6
ζ(β − 1) + ζ(β) +
e
3
3
6
Now we consider the general case when the subgraph induced by the vertices of degree
at least 2 is not 2-vertex connected. Let G = (V, E) be the power law graph and G0 =
(V 0 , E 0 ) the subgraph induced by {v ∈ V |degG (v) > 2}. Suppose that G0 consists of
2-vertex connected components G01 , . . . , G0L , which are connected in a tree-like manner
by bridges and/or articulation points. Then we run the Mömke-Svensson algorithm
separately on every component G0i = (Vi0 , Ei ), 1 6 i 6 L. Suppose that τ1 , . . . , τL are
the tours constructed in this way, and (Ri , Pi ), i = 1, . . . , L are the associated removable
P
P
pairs. Thus we have c(τi ) 6 43 |Ei | − 23 |Ri |. Now we observe that i |Ri | 6 i |Si | − 32 tβ eα .
Combined with our lower bound for the cost of a tour, this yields the following result.
Lemma 3. For 2 < β < 2.48, the approximation ratio of the Mömke-Svensson algorithm
2
ζ(β−1)+ 32 ζ(β)+ 65
on power-law Graphic instances is at most 31 +max{2,ζ(β)+
1 .
}
2

7

2

Finally we give an estimate for the performance of Mucha’s algorithm [Muc12] on
power law graphic instances. He shows that a tour can be constructed whose cost is at
x(E). Here x(E) denotes an optimum solution for the Held-Karp relaxation.
most 13 n + 10
9
Using this upper bound and the lower bound max{2, ζ(β) + 21 }, we obtain an A.R. of
1
ζ(β)
10
3
+ max{2,ζ(β)+
1 .
9
}
2

In Figure 2 we show the graphs of the approximation ratio for the MST
heuristic, Christofides’ algorithm, the Mömke-Svensson algorithm and Mucha’s algorithm
for power law Graphic instances.

M-S

1.8

approx. ratio

1.7
1.6
MST
1.5
7
5

1.4
Mu
1.3
Chr
1.2
1.5

2

2.5

β

Figure 2: Approximation ratios of the MST-algorithm (MST), Christofides’ algorithm
(Chr), Mucha’s algorithm (Mu) and the Mömke-Svensson algorithm (M-S) for Power
Law Graphic TSP for 1 < β < 2.48.

5

(1,2)-TSP on Power Law Graphs

We consider now an interesting further special case of Metric TSP, namely the (1, 2)TSP where the distances between cities are either one or two. More precisely, we are
given a complete undirected graph G = (V, E) together with an edge weight function
w : E → {1, 2}. The problem is known to be NP-hard and MAX-SNP-complete as
shown by Papadimitriou and Yannakakis in [PY93]. In the same paper they provided
an approximation algorithm with approximation ratio 67 . After more than a decade this
upper bound was slightly improved to 65
by Bläser and Shankar Ram in [BSR05]. The
56
current best approximation algorithm is due to Berman and Karpinski and achieves an
approximation ratio of 78 as stated in [BK06].
Now we consider the special case of the (1, 2)-TSP problem when the subgraph of
1-edges is an (α, β)-power law graph. In the following we refer to the subgraph of 1-edges
as the underlying graph.
8

5.1

Upper Bounds for Deterministic PLGs

Let G = (V, E) be the underlying graph. This means that for u 6= v, the distance between
u and v is 1 iff {u, v} ∈ E, otherwise the distance is 2. Now assume that G is an (α, β)PLG for some β > 1. In the following we make use of the methods and notations from
[PY93].
A cycle cover C of a graph G = (V, E) is a collection of vertex-disjoint cycles such
that each vertex v ∈ V is contained in a cycle of C. Suppose that there exists a cycle
cover C (also called a 2-matching) of cost n + k, where k is the number of 2-edges, such
that C does not contain any cycles of length less than four. An optimum cycle cover with
cycles of length at least four can be constructed efficiently [Har84; Man08].
Now let v1 , v2 , . . . , vn , v1 be an optimum tour. Let U be the set of nodes vi such that
d(vi , vi+1 ) = 2. We may assume that C contains at most one cycle which also contains
2-edges. All the other cycles of C are called pure. Let c2 be the number of pure cycles in C
which contain at least one node from U . In [PY93], two auxiliary graphs are constructed.
First, the bipartite graph B contains one node for each cycle from C and one node for
each vertex from V . A cycle node - here just denoted as C, where C ∈ C - is connected to
a node corresponding to vertex v ∈ V if v is not contained in C but there exists an edge
in G connecting v to a node in C. Let M be a maximum matching in B. The directed
graph F = (C, A) contains an arc (C, C 0 ) for every pair of cycles C, C 0 in C such that in
M , C is matched to a node in C 0 . Now F contains a spanning subgraph F 0 consisting
of directed paths of length 2, stars where there are directed edges from the leaves into
the center node of the star and isolated nodes. Let r2 be the number of pure cycles (i.e.
consisting only of 1-edges) which are isolated in F 0 . Let n2 denote the total number of
vertices which are contained in these cycles. Since all the cycles in C are of length at least
four, r2 6 n2 /4. Moreover, r2 6 c2 . In [PY93], a tour τ is constructed with
cost(τ ) 6 n + k +
Thus we obtain

2
(n − n2 − k) + r2
9

(1)

2
n2
(n − n2 − k) +
9
4
11
7
9−8
11
7
1
= n+ k+
n2 = n + k + c2
9
9
36
9
9
36
∗
Let τ denote an optimum tour. Then
cost(τ ) 6 n + k +

cost(τ ∗ ) > max{n + k, n + c2 }

(2)

We observe that for every x ∈ [0, 1], max{n + k, n + c2 } > (1 − x)(n + k) + x(n + c2 ).
This yields the following bound on the approximation ratio of this algorithm (for every
x ∈ [0, 1]):
11
1
n + 79 k + 36
c2
cost(τ )
9
6
cost(τ ∗ )
n + x(c2 − k) + k

Directly from the definition of c2 we obtain that c2 6 k. Therefore we choose x = 0 and
obtain
cost(τ )
6
cost(τ ∗ )

11
n
9

+



7
9

+

n+k

1
36



k
9

The right hand side of this inequality is monotone decreasing in k. Recall that k is the
number of 2-edges in a minimum length cycle cover.
For β > 1 we have n = ζ(β)eα . Moreover, the number of 2-edges in the optimum
cycle cover is at least half the number of degree 1 nodes in G. This yields
cost(τ )
6
cost(τ ∗ )

11
ζ(β)
9

+ 29
·
36
1
ζ(β) + 2

1
2

=

11
ζ(β)
9

+ 29
72
ζ(β) + 21

(3)

and thus the following theorem
Theorem 4. For β > 1, there exists an approximation algorithm for (1, 2)-TSP and
11
ζ(β)+ 29
underlying (α, β)-PLG with approximation ratio 9ζ(β)+ 172 .
2

In particular, for (α, β)-PLGs with power law exponent β > 1.666, the above theorem
yields an improvement over current best general (1, 2)-TSP bound of 87 due to [BK06]
(see Figure 3).

5.2

The Case of Large Exponents

Next we consider the asymptotic behaviour of the algorithm in [PY93] for large power
law exponents β → ∞. Recall that, for β > 2, ζ(β) eα is the total number of nodes and
eα is the number of degree 1 nodes. Since ζ(β) → 1 as β → ∞, at some point the number
of degree 1 nodes dominates the total number of nodes. This enforces that some fraction
of degree 1 nodes must be adjacent to other degree 1 nodes.
Let m1 be the number of degree 1 nodes which are adjacent to another node of degree
1. We have that
m1 > eα −vol([2, ∆]) = eα − (ζ(β − 1) eα − eα ) = (2 − ζ(β − 1)) eα
The right hand side of this inequality is strictly positive for β > 2.729. Since every
degree 1 node contributes an amount of 1.5 to the cost of a tour and the contribution of
every other node is at least one, the cost of any tour is at least eα ·1.5 + (ζ(β) − 1) eα .
On the other hand, we can construct a tour containing m21 edges connecting degree 1
nodes by first contracting all these edges and then applying any TSP algorithm to the
residual instance. Since the contribution of every other node is at most 2, we obtain an
approximation ratio of
3
m + 2(ζ(β) eα −m1 )
2 1
3 α
e +(ζ(β) − 1) eα
2

2ζ(β) eα − 21 m1
= 3 α
e +(ζ(β) − 1) eα
2
6
=

2ζ(β) eα − 21 (2 − ζ(β − 1)) eα
3 α
e +(ζ(β) − 1) eα
2

2ζ(β) + 12 ζ(β − 1) − 1
ζ(β) + 12

This yields the following theorem.
Theorem 5. For β > 2.729, there exists an approximation algorithm for (1, 2)-TSP and
2ζ(β)+ 21 ζ(β−1)−1
underlying (α, β)-PLG with approximation ratio
.
ζ(β)+ 1
2

10

In Figure 3 we plot the approximation ratios for the deterministic case and the case
of large exponents in comparison with the current best general upper bound of 87 due
to [BK06]. We observe that an improvement over 87 is achieved for β > 3.765 and an
improvement over the bound a(β) of Theorem 4 is achieved for β > 4.309.

1.4

approx. ratio

1.3
ã(β) =

2·ζ(β)+ 12 ζ(β−1)−1
ζ(β)+ 12

1.2
8
7

a(β) =

1.1

1

2

3

4

5
β

6

11
ζ(β)+ 29
9
72
ζ(β)+ 12

7

8

9

Figure 3: Approximation ratios for the Power Law (1, 2)-TSP as of Theorem 4, a(β) =
29
11
ζ(β)+ 72
2ζ(β)+ 12 ζ(β−1)−1
9
,
and
Theorem
5
(ã(β)
=
) in comparison with the upper bound
1
ζ(β)+
ζ(β)+ 1

of

8
7

5.3

2

due to [BK06].

2

Improved Upper Bounds for Random PLGs

Now we consider the case when the underlying graph G is a random PLG. At first we
present our general idea that will then yield improved approximation ratios for (1, 2)-TSP
with underlying random (α, β)-PLG.
In the case of deterministic PLGs we have already made use of the following observation. The cost of a tour τ can be written as the sum of node costs cτ (v), where cτ (v)
is defined as 21 times the cost of edges incident to v in τ . In the case of the (1, 2)-TSP,
cτ (v) > 1, since any of the two incident edges has cost at least 1. Moreover, if v is a
node of degree 1, then cτ (v) > 3/2, since at least one of the two edges incident to v has
α
cost 2. This yields a lower bound k > e2 (see Section 5.1). Now we want to improve
this lower bound by taking into account the expected number of low degree neighbors
of nodes in an underlying random PLG. Let Γi (v) be the set of degree i neighbors of
P
node v and Ni (v) = |Γi (v)| its cardinality. Let Ni (V ) = v∈V Ni (v). Now we let A1 (v)
denote the additional lower bound of k generated by degree 1 neighbors of v, namely
11

A1 (v) = minτ u∈Γ1 (v) (cτ (u) − 3/2), where the minimum is over all tours τ . For a set
P
U ⊆ V of nodes we write A1 (U ) = v∈U A1 (v). Below we will show that A1 (v) > N12(v) −1.
We will also take into account the additional lower bound on the tour cost generated by
degree 2 neighbors of a node v. This lower bound is inherently tour-dependent and will
be denoted as A2,τ (v), where v is a node of degree > 2 and τ is a tour. It turns out that
the values A2,τ (v) are not independent from each other, and we will only be able to give
a lower bound on the sum A2,τ (V ).
Let us first consider the case i = 1. For the degree 1 nodes we already accounted
α
a value of 12 for each node for our lower bound k > e2 . Now suppose that a node v of
degree i has j 6 i degree 1 neighbors. This provides an additional value of 12 for j − 2
neighbors since any tour τ uses at most two 1-edges connecting v. The remaining j − 2
neighbors are connected via 2-edges. In Figure 4 we depict the situation around a node
v with j degree 1 neighbors.
P

j

...

...

v

v

Figure 4: (left) Node v with j degree 1 neighbors. (right) A possible tour around v which
enters and leaves v via degree 1 neighbors and matches the remaining degree 1 vertices
via 2-edges. Since we already accounted 12 for every degree 1 vertex, this introduces an
additional value of A1 (v) = 2j − 1.
Now we turn to the case i = 2. We will first give a definition of the terms A2,τ (v). Then
we will prove that for every tour τ the two inequalities c(τ ) > n + eα /2 + A1 (V ) + A2,τ (V )
P
and A2,τ (V ) > deg(v)>2 12 · (N2 (v) − 2) hold. Recall that for a tour τ and a node v ∈ V ,
the tour cost of v, cτ (v) is defined as the sum of half of all the edge costs of tour edges
incident to v. The set of neighbors of v in G is denoted as ΓG (v). Moreover, we let Γτ (v)
denote the set of nodes which are adjacent to v in the tour τ . Γ2,τ (v) denotes the set of
nodes of degree 2 in G which are adjacent to v in τ . For nodes v ∈ V of degree deg(v) > 2
we let
A2,τ (v) =

X
u∈ΓG (v)\Γ2,τ (v)

|{v 0 |deg(v 0 )

cτ (u) − 1
,
> 2, v 0 ∈ ΓG (u) \ Γτ (u)}|

and A2,τ (v) = 0 otherwise. The following lemma shows that using the values A1 (v), A2,τ (v),
we obtain a lower bound for the cost of a given tour τ .
Lemma 6. For every tour τ , c(τ ) > n +
Proof. We let A1,τ (v) =

u∈Γ1 (v) (cτ (u)

P

eα
2

+ A1 (V ) + A2,τ (v).

− 3/2). We observe that for every node v in G,

12

cτ (v) > 1, and for every node u of degree 1, cτ (u) > 3/2. We obtain
c(τ ) =

X

cτ (v)

v

>n+

X
X
eα
+
(cτ (u) − 3/2) +
(cτ (u) − 1)
2
deg(u)=1
deg(u)=2

>n+

X
X
X
eα
+
(cτ (u) − 3/2) +
(cτ (u) − 1)
2
deg(v)>2 u∈Γ1 (v)
deg(u)=2

We observe that for every node u of degree 2,
cτ (u) − 1 =

X
v∈ΓG (u)\Γτ (u),deg(v)>2

|{v 0 |deg(v 0 )

cτ (u) − 1
> 2, v 0 ∈ ΓG (u) \ Γτ (u)}|

This concludes the proof of the lemma.
Now assume that a node v of degree > 2 has l degree 2 neighbors. Again, any tour τ
uses at most two 1-edges while visiting v. The remaining l − 2 neighbors may be entered
via 1-edges but then only left via 2-edges for which we may account an additional value
of 12 . In Figure 5 we depicted the situation around a node v with l neighbors of degree 2.
l

...

...

v

v

Figure 5: (left) Node v with l degree 2 neighbors. (right) A possible tour around v which
enters and leaves v via degree 2 neighbors and matches the remaining degree 2 vertices
pairwise via 2-edges. This introduces an additional value of A2 (v) = 2l − 1.
We will now prove the following lower bound on the contribution of degree 2 neighbors
to the cost of a tour.
Lemma 7. For every tour τ , A2,τ (V ) =

P

v,deg(v)>2

A2,τ (v) >

1
deg(v)>2 2

P

· (N2 (v) − 2).

Proof. Consider a pair of nodes v, u with deg(v) > deg(u) = 2 such that u and v are
adjacent in G but not in τ . Let v 0 be the other neighbor of u. Since v is not adjacent to u
in the tour τ , the node u is incident to at least one tour edge of cost 2. Now we consider
three different cases concerning the other neighbor v 0 . If v 0 is a node of degree 6 2, then
we do not have to charge anything to v 0 , and thus we can charge cτ (u) − 1 > 3/2 − 1 = 1/2
to v. If v 0 is a node of degree > 2 which is adjacent to u within the tour τ , we can also
charge cτ (u) − 1 > 1/2 to v. In the remaining case, v 0 is a node of degree > 2 which is
not adjacent to u in τ . But then u is incident to two edges of cost 2 in τ , which implies
13

cτ (u) − 1 = 2 − 1 = 1, and we can charge 1/2 to v and 1/2 to v 0 . The same holds when
v = v 0 and u is not adjacent to v in τ . Finally we observe that for every node v of degree
> 2, all but at most two degree 2 neighbors of v are not adjacent to v in τ . This concludes
the proof of the lemma.
In the following we quantify the effect of the above considerations and the resulting
upper approximation bounds for the case of (1, 2)-TSP and underlying random (α, β)PLGs. We present separate analyses for the three subcases β > 2, β = 2 and 1 < β < 2.
Resulting Upper Bounds for β > 2 We are going to estimate the value A1 (V ) for
the case that the underlying graph is an (α, β) power law graph Gα,β = (V, E) and for
power law exponents β > 2. We show the following lemma.
Lemma 8. Let β > 2 and Gα,β = (V, E) ∈ Gα,β be a random PLG in the P (α, β) model.
We have that
eα
E[A1 (V )] >
ζ(β − 1)β−1 2β−1

1
1
−
.
(β − 2)(β − 1) 4ζ(β − 1)
!

Proof. First we give a lower bound for the expected number of degree 1 neighbors of a
node v of degree i.
E[N1 (v)] =

i
X

Pr(j-th neighbor has deg. 1)

j=1
e
X
α

=

Pr(the j-th deg. 1 node will be adjacent to v)

j=1

= eα

i
i
i
=
>
ζ(β − 1) eα −1
ζ(β − 1) − e−α
ζ(β − 1)

Thus, the expected additional value for a node v of degree i contributing to k is E[A1 (v)] =
i
− 1. This value is positive for i > 2ζ(β − 1). Summing up over all vertices with
2ζ(β−1)
sufficiently large degrees, we obtain
∆
X

eα
E[A1 (V )] >
iβ
i=2ζ(β−1)

!

i
−1
2ζ(β − 1)

(4)

Replacing the sums in (4) by the corresponding integral, we get the following lower bound
on E[A2 (V )]:
E[A1 (V )] >



e


2ζ(β − 1)
α

Z∆

2ζ(β−1)



− eα 


Z∆

2ζ(β−1)

1
xβ−1

dx +

1
2


!
1


β−1

1
−
(2ζ(β − 1))β−1 ∆


1
1
1 
eα


+
−
+

∆
xβ (2ζ(β − 1))β ∆β
∆β 2ζ(β−1)
−1

14

The anti-derivative now has the following form
E[A1 (V )] >

e
x

2ζ(β − 1)
2−β
"

α

"

1−β

x
− eα 
1−β

2−β

#∆

+

2ζ(β−1)

1
2

#∆

1
1
− β−1 
β−1
(2ζ(β − 1))
∆
!

1
1 
∆
+
−1
−
+
(2ζ(β − 1))β ∆β
2ζ(β − 1)
2ζ(β−1)


eα
=
2ζ(β − 1)

1
1
1
1
−
+ β
−
β−2
β−2
β−1
(β − 2)(2ζ(β − 1))
(β − 2)∆
2 ζ(β − 1)
2∆β−1
!
1
1
1
1
− eα
−
+ β
− β + o(eα )
β−1
β−1
β
(β − 1)(2ζ(β − 1))
(β − 1)∆
2 ζ(β − 1)
∆
!
1
1
1
1
eα
+
−
−
− o(1)
=
ζ(β − 1)β−1 2β−1 β − 2 4ζ(β − 1) β − 1 2ζ(β − 1)
!
1
eα
1
−
=
ζ(β − 1)β−1 2β−1 (β − 2)(β − 1) 4ζ(β − 1)

!

This concludes the proof of the lemma.
Next, we want to further improve the expected lower bound on k similar to Lemma 8
by taking into account the additional value generated by degree 2 neighbors of nodes in
the underlying graph Gα,β .
Let A2 (V ) be the value added by degree 2 neighbors of nodes in the underlying graph
G = (V, E). We prove the following lemma.
Lemma 9. Let Gα,β = (V, E) ∈ Gα,β be a random PLG in the P (α, β) model. We have
that
E[A2 (V )] > (1 − o(1)) e

α

2−β(β−1) ζ(β − 1)1−β
1
+
(β − 1)(β − 2)
ζ(β − 1)β



1

2β·β+1

1
− 2β
2

!

.

Proof. First we give a lower bound for the expected number of degree 2 neighbors of a
node v of degree i.
E[N2 (v)] =

i
X

Pr(j-th neighbor has deg. 2)

j=1
eα

=

2β
X

Pr(the j-th deg. 2 node will be adjacent to v)

j=1

eα
i
ζ(β − 1) eα −1 − i
i
= β
+
·
α
α
2 ζ(β − 1) e −1
ζ(β − 1) e −1
ζ(β − 1) eα −2
eα
2i
i
> β·
= β−1
α
2 ζ(β − 1) e
2 ζ(β − 1)

!

Now, the expected additional value for a node v of degree i contributing to k is E[A2 (v)] =
i
− 1. This value is positive for i > 2β ζ(β − 1). Summing up over all vertices with
2β ζ(β−1)
15

sufficiently large degrees, we obtain
∆
X

eα
E[A2 (V )] >
iβ
i=2β ζ(β−1)
=

!

i
−1
β
2 ζ(β − 1)

∆
∆
X
X
eα
1
1
α
−
e
.
β
β−1
2 ζ(β − 1) i=2β ζ(β−1) i
iβ
i=2β ζ(β−1)

(5)

Replacing the sums in (5) by the corresponding integral, we obtain the inequality
E[A2 (V )] >

e



α

2β ζ(β

− 1)


− eα 





1

∆β−1

1
+
∆β

Z∆

+

x1−β dx +

2β ζ(β−1)

Z∆

1
2

(2β ζ(β


!
1


β−1

1
−
− 1))β−1 ∆


x−β dx +

2β ζ(β−1)

1
1
− β

β
− 1))
∆

(2β ζ(β

The anti-derivative now has the following form
eα
x2−β

E[A2 (V )] > β
2 ζ(β − 1)
2−β
"

x1−β
− eα 
1−β
"

#∆

1 
1
+
+ β(β−1)+1
β−1
2
ζ(β − 1)
2∆β−1
2β ζ(β−1)


#∆

1

+ 2β
β
2
ζ(β
−
1)
β
2 ζ(β−1)


eα
(2β ζ(β − 1))2−β − ∆2−β
1
1
= β
+ β(β−1)+1
+
β−1
2 ζ(β − 1)
β−2
2
ζ(β − 1)
2∆β−1
!
β
1−β
1
− ∆1−β
α (2 ζ(β − 1))
+ 2β
−e
β−1
2 ζ(β − 1)β
1
1
1
= eα
+ β·β+1
−
β(β−1)
β
β(β−1)
(β − 2)2
ζ(β − 1) 2
ζ(β − 1)
(β − 1)2
ζ(β − 1)
!
1
− 2β
− o(1)
2 ζ(β − 1)β

!

= (1 − o(1)) e

α

2−β(β−1) ζ(β − 1)1−β
1
+
(β − 1)(β − 2)
ζ(β − 1)β



1

2β·β+1

1
− 2β
2

!

This concludes the proof of the lemma.
From Lemma 8 and Lemma 9 we obtain the following corollary.
Corollary. Let k be the number of 2-edges in the optimum cycle cover of a (1, 2)-TSP
instance with underlying power law graph Gα,β ∈ Gα,β drawn from P (α, β). We have
eα
+ E[A1 (V )] + E[A2 (V )]
2
!
eα
eα
1
1
>
+
−
2
ζ(β − 1)β−1 2β−1 (β − 2)(β − 1) 4ζ(β − 1)

E[k] >

+e

α

2−β(β−1) ζ(β − 1)1−β
1
+
(β − 1)(β − 2)
ζ(β − 1)β
16



1

2β·β+1

1
− 2β
2

!

=: Ek

From the above corollary we finally obtain
Theorem 10. For β > 2, there exists an approximation algorithm for (1, 2)-TSP and
11
ζ(β)+ 29
·Ek
36
.
underlying random (α, β)-PLG with expected approximation ratio 9 ζ(β)+E
k
In Figure 7 we compare the expected approximation ratio â(β) of Theorem 10 to the
ratio a(β) achieved in the deterministic setting (Theorem 4).

expected approx. ratio

a(β) =

11
29
ζ(β)+ 72
9
ζ(β)+ 12

1.1

â(β) =

11
29
ζ(β)+ 36
·Ek
9
ζ(β)+Ek

1.075

3

4

5

6

7

β

Figure 6: Plot of the expected approximation ratio â(β) of Theorem 10 as compared to
the ratio a(β) achieved in the deterministic setting (Theorem 4).
Resulting Upper Bound for 1 < β < 2 We consider now the case when the power law
exponent β satisfies 1 < β < 2. Again we will give estimates for the expected additional
contribution of degree 1 and degree 2 nodes A1 (V ) and A2 (V ). The contribution of degree
1 nodes is given in the following lemma.
Lemma 11. Let 1 < β < 2 and Gα,β = (V, E) ∈ Gα,β be a random PLG in the P (α, β)
model. We have that E[A1 (V )] > eα .
The proof is similar to that of Lemma 8. The expected number of degree 1 neighbors
deg(v)
of a node v can be lower bounded by eα 2|E|−1
> (2 − β)deg(v) eα(1−2/β) . Based on this we
obtain
E[A1 (V )] >

eα
+
2

∆
X
4
2−β

eα(2/β−1)

2 − β 1−β α(2−2/β)
j
e
.
2
17

We estimate the sums by integrals and finally obtain E[A1 (V )] > eα .
The case of degree 2 nodes being adjacent to nodes of higher degree is considered in
the following lemma.
Lemma 12. Let 1 < β < 2 and Gα,β = (V, E) ∈ Gα,β be a random PLG in the P (α, β)
model. We have that E[A2 (V )] > 41 eα .
Proof. We start by estimating the expected number of degree 2 neighbors of high degree
nodes in Gα,β . Suppose v is a node of degree i. Then we have
eα
i
+
E[N2 (v)] = β  e2α/β
2
−1
2−β


e2α/β
−1−
2−β
e2α/β
−1
2−β

i

·



i
e2α/β
2−β

−2



(2 − β) eα
i
i
2−β
· α( 2 −1)
· 2α/β =
β
2
e
2
e β
Therefore, the expected additional contribution to k generated by a node v of degree i
i
4
in Gα,β is E[A2 (v)] = 2−β
· eα(2/β−1)
=: δ.
− 1. This value is positive for i > eα(2/β−1) · 2−β
4
Summing up over all nodes with sufficiently large degrees we obtain
>

E[A2 (V )] =
>

∆
X
eα
δ
∆
X

iβ

i
2−β
· α(2/β−1) − 1
4
e

!

2−β
i1−β
eα
· 2α(1/β−1) − β
4
e
i

δ

!

We replace the sum by the corresponding integral, we obtain
E[A2 (V )] >

∆+1
Z
δ

4
2 − β 2α(1−1/β) 2 − β 2α(1−1/β) 
e
+
e
eα(2/β−1)
x1−β dx ·
4
8
2−β


 ∆+1
Z
x−β dx +
− (∆ + 1)1−β  − eα 


δ

4
eα(2/β−1)
2−β

!−β

!1−β



− (∆ + 1)−β 

Again we make use of anti-derivatives in order to estimate the integral terms. Then
by rearranging terms we obtain E[A2 (V )] > 1/4 eα . This concludes the proof of the
lemma.
From the above Lemma 11 and Lemma 12 we obtain the following result.
Theorem 13. For 1 < β < 2, there exists an approximation algorithm for (1, 2)-TSP
11
ζ(β)+ 29 · 45
and underlying random (α, β)-PLG with approximation ratio 9 ζ(β)+36
.
5
4

Resulting Upper Bound for β = 2 In the case when the power law exponent is
β = 2, we proceed similarly and obtain the following result.
Theorem 14. For β = 2, there exists an approximation algorithm for (1, 2)-TSP and
11
ζ(β)+ 29 · 58
underlying random (α, β)-PLG with approximation ratio 9 ζ(β)+36
.
5
8

Figure 7 shows the approximation ratio for (1, 2)-TSP on random (α, β)-PLGs for the
three subcases 1 < β < 2, β = 2 and β > 2.
18

a(β) =

expected approx. ratio

1.1

ã(β) =

11
ζ(2)+ 145
9
288
ζ(2)+ 58

11
145
ζ(β)+ 144
9
5
ζ(β)+ 4

â(β) =

11
ζ(β)+ 29
·Ek
9
36
ζ(β)+Ek

1.075

1.05
1.5

2

2.5

3

β

Figure 7: Expected Approximation ratio for Random Power Law (1, 2)-TSP for 1 < β < 2
(ã(β), Theorem 13), β = 2 (a(β), Theorem 14) and β > 2 (â(β), Theorem 10).

5.4

Lower Bounds

In this section we give the first approximation lower bounds for TSP in (1, 2)-PLG instances. The approximation hardness of the general (1, 2)-TSP problem was proven in
[PY93]. Later the first explicit inapproximability bounds of 5381/5380 was proven by Engebretsen [Eng03], and further improved step by step to the current best bound of 123/122 by
Karpinski, Lampis, and Schmied [KLS13] applying the results of Berman and Karpinski
[BK99], [BK01].
Our overall approach is to construct appropriate reductions from the (1, 2)-Metric TSP
to (1, 2)-metric instances whose underlying graph is a PLG. We make use of the lower
bound constructions developed in [KS13a] (see also [EK06; Lam12; KS13b; KLS13]). The
reduction in [KS13a] starts from a special bounded occurrence optimization problem.
Definition 5.1 (Hybrid Problem). Given a system of linear equations mod 2 over n
variables, m2 equations with exactly two variables, and m3 equations with exactly three
variables, find an assignment to the variables that maximizes the number of satisfied
equations.
The approximation hardness of the above problem was proven by Berman and Karpinski in [BK99] using a result of Håstad in [Hås01]. They proved the following theorem.
Theorem 15 ([BK99]). For every 0 < ε < 12 , there exists an instance IH of the Hybrid
problem with 42v variables, m2 = 60v, m3 = 2v such that every variable occurs exactly 3
times and it is NP-hard to decide whether IH has its optimum value above (62 − ε)v or
below (61 + ε)v.
19

The above result is used in the following reduction from Hybrid to Subcubic (1, 2)TSP due to Karpinski and Schmied [KS13a]. Later we present our new reduction from
slightly modified Subcubic (1, 2)-TSP instances to (1, 2)-TSP instances with underlying
PLG.
Reduction from Hybrid to Subcubic (1, 2)-TSP The reduction starts from Hybrid
instances with 60v 2-equations, 2v 3-equations and 42v variables. In [KS13a], these
instances have been mapped to (1, 2)-TSP instances G12
SC with
60v · 8 + 2v · (9 · 8 + 6 · 3 + 2 · 3) = v · 672
nodes. Our aim is to modify these instances slightly in order to fit them into a power law
degree distribution. The instances G12
SC consist of building blocks called parity gadgets.
A parity gadget is a graph P with 8 nodes being connected as shown in Figure 8.

Figure 8: Parity gadget.
The graph G12
SC contains
• one parity gadget for every variable,
• one additional parity gadget for every 2-equation,
• for every 3-equation a subgraph involving the parity gadgets for the variables being
involved, additionally 6 parity gadgets and 12 extra nodes.
Let us describe the simulating gadget for a 3-equation x ⊕ y ⊕ z = 0, as constructed
in [KS13a]. Given an equation of the form x ⊕ y ⊕ z = 0, three clauses (x ∨ a1 ∨ a2 ),
(y ∨ a2 ∨ a3 ) and (z ∨ a1 ∨ a3 ) are created. Note that for any given assignment to x, y
and z satisfying the equation mod 2, it is possible to find an assignment of a1 , a2 and a3
that satisfies all clauses. Otherwise any assignment to a1 , a2 and a3 satisfies at most two
clauses. The clause gadget as constructed in [KS13a] is shown in Figure 9.
In order to complete the construction for an equation x⊕y⊕z = 0, [KS13a] introduced
a gadget to simulate equations of the form a11 ⊕ a21 = 0. The construction is shown in
Figure 10.
This completes the modular description of the reduction of Hybrid instances IH to
Subcubic (1, 2)-TSP instances G12
SC . For further details we refer to [KS13a].
Subcubic (1, 2)-TSP and Perfect Matchings Next, we modify the above instances
G12
SC to permit a perfect matching in order to prepare our reduction to (1, 2)-TSP instances
with underlying PLG. First we observe that the subgraphs corresponding to parity gadgets (cf. Figure 8) and the subgraphs corresponding to equations of the form x ⊕ y = 0
already contain a perfect matching.
20

c1

c1

c3

c3
x

smid

s∨

e∨

smid

s∨

z

e∨

y
c2

c2

Figure 9: The gadget corresponding to clauses (x ∨ y ∨ z) in detailed and modular view.
y

x
s1∨

s1=

a11

a11

a21

a12 e1
∨

s2∨

e1=

s2=

z

a21

a12

a22 e2
∨

s3∨

e2=

s3=

a22

a32 e3
∨

a31

a13

a23

e3=

Figure 10: Modular view of the gadget simulating x ⊕ y ⊕ z = 0.
Now we consider the clause gadget simulating (x ∨ y ∨ z) as shown in Figure 9. It uses
three isomorphic copies of a parity gadget and contains 6 extra nodes, namely s∨ , smid ,
e∨ , c1 , c2 and c3 (cf. Figure 9). These extra nodes are of degree 3. If we replace two such
extra nodes v by a separate copy of the graph K4 and connect three of the four nodes
to the neighbors of v as shown in Figure 11, then the resulting modified gadget has the
additional property that it contains a perfect matching.
12
If we let G̃12
SC the graph which is obtained from GSC by applying all these modi12
fications, then we conclude that G̃SC contains a perfect matching which we denote as
M.
The modified instances G̃12
SC have 2 · (60v + 2v · 9) = 156v nodes of degree 2, 6 · (60v +
2v · 9) + 2v · (6 · 3 + 6) = 516v nodes of degree 3 and 3 · 2 · ]Gv = 3 · 6 · 2v = 36v nodes of
degree 4.
Thus we have a mapping
Hybrid−→Subcubic (1, 2)-TSP−→(1, 2)-TSP
IH

7−→

G12
SC

7−→

G̃12
SC

12
where G̃12
SC is a graph of maximum degree 4. The resulting instance G̃SC has 708v
vertices, namely 156v of degree 2, 516 of degree 3 and 36v of degree 4. It is hard to
decide if τ > 709v or τ 6 708v.

21

3)

c3

s∨

smid

e∨

z

7→

s∨

c3
x

(3,

x

c1

(3, 3)

c1

smid

y

z

e∨

y

c2

c2

Figure 11: The modified gadget for clauses (x ∨ y ∨ z) that contains a perfect matching.
Reduction to Power Law (1, 2)-TSP Now those instances have to be embedded into
power law graphs. The instance G̃12
SC has a perfect matching M , which we want to use in
order to embed G̃12
into
a
power
law graph. Thus we have to give a precise description
SC
of the node degrees of pairs of nodes which are connected by matching edges. Let us
make use of the following notation: We say an edge e is of type (a, b) if e = {u, v}, the
degree of u is a and the degree of v is b. We observe that inside each parity gadget P ,
M contains 2 edges of type (3, 3) and 2 edges of type (2, 3).
Moreover, M contains for every 3-equation 2 · 3 + 3 edges of type (3, 3), 2 · 3 edges of
type (3, 4) and 2 · 3 edges of type (4, 4).
Thus in total M consists of the following edges:
• edges of type (2, 3): 2 · ]P = 2 · (2v · 9 + 60v) = 2 · 78v = 156v
• edges of type (3, 3): 2 · ]P + 9 · ]3-eq = 18v + 2 · 78v = 174v
• edges of type (3, 4): 6 · ]3-eq = 12v
• edges of type (4, 4): 6 · ]3-eq = 12v
We want to embed G̃12
SC into an interval [δ, ∆] of a power law distribution, where δ is
a parameter of this construction. In order to fit G̃12
SC into [δ, ∆], we replace the edges of
M by multi-edges. Let µ : M → N such that for e ∈ M , µ(e) is the multiplicity of edge
e.
Let us first consider the special case when µ : M → {1}. In that case, we have to
minimize α such as to satisfy the following inequalities:
156v 6

eα
,
2β

(156 + 174 · 2 + 12)v 6

eα
,
3β

(12 + 2 · 12)v 6

eα
,
4β

or equivalently eα > max{2β ·156v, 3β ·516v, 4β ·36v}. We first observe that for β 6

log( 516
36 )
log( 43 )

,

this is equivalent to e > 3 · 516v. Suppose now that we have chosen α such that
ζ(β)eα = ζ(β) · 3β · 516v. The power law graph Gα,β is the union of µ(G̃12
SC ), a matching
W1 on all but at most one degree 1 nodes and a graph W consisting of the remaining nodes
of degree at least 2 and at most one degree-1 node. The graph W can be constructed in
such a way that it contains a TSP path consisting of edges of cost one (cf. [GHK15]).
Let |W | denote the number of nodes in the graph W . Then we may assume every tour
α

β

22

τ of the (1, 2)-metric space defined by Gα,β to consist of a TSP path τSC of G̃12
SC , a path
3
α
in W and a path of cost at most 2 · e −1 connecting the degree-1 nodes in W1 and three
edges of cost 2 connecting these paths. The cost of the TSP path in W is asymptotically
equal to |W | − 1. Thus the cost of the tour τ satisfies
3
c(τ ) = c(τSC ) + |W | + eα + O(1).
2
We have |G̃12
SC | = 708v = 708 ·


|W | = ζ(β) − 1 −

ζ(β)eα
ζ(β)·3β ·516

and

708
eα
516 · 3β


Thus it is NP-hard to decide if the cost of an optimum tour τ ∗ in Gα,β satisfies
708
eα
3
+ ζ(β) − 1 −
c(τ ) 6 708 · β
eα + · eα + O(1)
β
3 · 516
516 · 3
2


∗

or



1
708
eα
+ ζ(β) + −
c(τ ) > 709 · β
eα − O(1).
3 · 516
2 516 · 3β


∗



log( 516 )
For β > log(364 ) , we obtain the requirement eα > 4β · 36v and proceed in the same
3
way. We obtain the following result.

Theorem 16. For 1 < β 6

log( 516
36 )
log( 34 )

, the (1, 2)-TSP on (α, β)-Power Law Graphs is

/2)+1
NP-hard to approximate within any factor less than 3 3·516·(ζ(β)+
β ·516·(ζ(β)+1/2) .
log( 516 )
For β > log(364 ) , the (1, 2)-TSP on (α, β)-Power Law Graphs is NP-hard to approxi3

mate within any factor less than

β

1

4β ·36·(ζ(β)+1/2)+1
.
4β ·36·(ζ(β)+1/2)

Now we improve on this result and consider the general case when µ : M → N. We
consider an embedding which we call Even-Degree Packing for a given α. We choose edge
multiplicities µ(e) for e = {u, v} such that when d(u) + µ(e) − 1 6 d(v) + µ(e) − 1 6
d(u) + µ(e), then d(u) + µ(e) − 1 is even. This means that we partition the interval [2, ∆]
into subintervals of size 2 of the form [2i, 2i + 1] and construct the edge multiplicities µ
in such a way that we always have µ(e) ≡ d(u) − 1 mod 2. Suppose the degrees which
are occupied in this way are of the form 2i, 1 6 i 6 x∆. Then the sum of multiplicities
of edges which we can pack in this way is
x∆
X
i=1

$

x∆
X
eα
eα
>
− x∆
β
(2i + 1)β
i=1 (2i + 1)

%

>

x∆+1
Z
1



eα
eα
1−β
1−β
dy
−
x∆
=
3
−
(2x∆
+
3)
− x∆
(2y + 1)β
2(β − 1)

with x 6 21 · ∆−1
. Thus it suffices to choose α such that
∆
1 ∆−1
x = 2 · ∆ , this is equivalent to
eα
1
1
− · (eα )1/β + > 354v
β−1
3
· 2(β − 1) 2
2
23

eα
2(β−1)

·

1
3β−1

− x∆ > 354v. For

Now the cost of a tour τ is c(τ ) = c(τSC ) + |W | + 23 eα + 3, and we have |G̃12
SC | = 708v =
eα
708 · 3β−1 ·2(β−1)·354 . The size of the set W is given as
|W | = (ζ(β) − 1)e −
α

|G̃12
SC |

708
= ζ(β) − 1 − β−1
3
· 2(β − 1) · 354

!

Thus it is NP-hard to decide if
eα
708
3
c(τ ) 6 708 · β−1
+ ζ(β) − 1 − β−1
eα + eα + O(1)
3
· 2(β − 1) · 354
3
· 2(β − 1) · 354
2
!

∗

or
eα
1
708
c(τ ) > 709 · β−1
+ ζ(β) + − β−1
eα − O(1)
3
· 2(β − 1) · 354
2 3
· 2(β − 1) · 354
!

∗

We obtain the following result.
Theorem 17. The (1,2)-TSP on (α, β)-Power Law Graphs is NP-hard to approximate
1/2)·3β−1 ·2(β−1)·354+1
.
within any factor less than (ζ(β)+
(ζ(β)+1/2)·3β−1 ·2(β−1)·354

In Figure 12 we plot and compare the resulting lower bounds of Theorem 16 and
Theorem 17 for the (1, 2)-TSP with underlying (α, β)-PLG.
1.0011
1.001
1.0009
lower bound

1.0008
1.0007
1.0006
1.0005
(ζ(β)+ 12 )·3β−1 ·2(β−1)·354+1
(ζ(β)+ 12 )·3β−1 ·2(β−1)·354

1.0004
1.0003
1.0002
1.0001

3β ·516·(ζ(β)+ 12 )+1
3β ·516·(ζ(β)+ 12 )

1.5

2

2.5

3

β

Figure 12: Plot of the lower bounds due to Theorem 16 and Theorem 17.

24

6

Further Research

It remains an interesting open problem on improving our approximability results as well
as their extension to other related cases. It would be very interesting to shed some more
light on the structural properties of the underlying problems.

References
[ACL01]

W. Aiello, F. Chung, and L. Lu. “A random graph model for power law
graphs”. Experimental Mathematics 10.1 (2001), pp. 53–66.

[AT15]

Approximation Taxonomy of Metric TSP. 2015. url: http://theory.cs.
uni-bonn.de/info5/tsp/ (visited on 08/25/2015).

[BK99]

P. Berman and M. Karpinski. “On some tighter inapproximability results”.
English. Proceedings of the 26th international Conference on Automata, Languages and Programming. Ed. by J. Wiedermann, P. Emde Boas, and M.
Nielsen. Vol. 1644. ICALP ’99. Springer-Verlag, 1999, pp. 200–209.

[BK01]

P. Berman and M. Karpinski. “Efficient amplifiers and bounded degree optimization”. ECCC TR01-053 (2001).

[BK06]

P. Berman and M. Karpinski. “8/7-Approximation Algorithm for (1,2)-TSP”.
Proceedings of the 17th annual ACM-SIAM Symposium on Discrete Algorithms. 01/2006, pp. 641–648.

[BSR05]

M. Bläser and L. Shankar Ram. “An improved approximation algorithm for
TSP with distances one and two”. Proceedings of the 15th International Symposium on Fundamentals of Computation Theory. Vol. LNCS 3623. FCT ’05.
Springer, 2005, pp. 504–515.

[Chr76]

N. Christofides. Worst-Case Analysis of a New Heuristic for the Travelling
Salesman Problem. Tech. rep. CS-93-13, Carnegie-Mellon University, Pittsburgh, 1976.

[Eng03]

L. Engebretsen. “An Explicit Lower Bound for TSP with Distances One and
Two”. Algorithmica 35.4 (04/2003), pp. 301–319.

[EK06]

L. Engebretsen and M. Karpinski. “TSP with Bounded Metrics”. Journal of
Computer and System Sciences 72.4 (06/2006), pp. 509–546.

[GHK15] M. Gast, M. Hauptmann, and M. Karpinski. “Inapproximability of dominating set on power law graphs”. Theoretical Computer Science 562 (01/2015),
pp. 436–452.
[GSS11]

S. O. Gharan, A. Saberi, and M. Singh. “A Randomized Rounding Approach
to the Traveling Salesman Problem”. English. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science. FOCS. IEEE,
10/2011, pp. 550–559.

[Har84]

D. B. Hartvigsen. “Extensions of matching theory”. PhD thesis. CarnegieMellon University, 1984.

25

[Hås01]

J. Håstad. “Some optimal inapproximability results”. Journal of the ACM
48.4 (07/2001), pp. 798–859.

[Kar15]

M. Karpinski. “Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies”. Proceedings of the 20th International Symposium on Fundamentals of Computation Theory. Vol. LNCS 9210. 2015, pp. 3–
11.

[KLS13]

M. Karpinski, M. Lampis, and R. Schmied. “New Inapproximability Bounds
for TSP”. Algorithms and Computation. Vol. 8283. Lecture Notes in Computer
Science. 2013, pp. 568–578.

[KS13a]

M. Karpinski and R. Schmied. “Approximation Hardness of Graphic TSP on
Cubic Graphs”. arXiv preprint arXiv:1304.6800 (04/2013), p. 19. arXiv:1304.
6800.

[KS13b]

M. Karpinski and R. Schmied. “Improved Inapproximability Results for the
Shortest Superstring and Related Problems”. Proceedings of the 19th Computing: The Australasian Theory Symposium, CRPIT 141. 01/2013, pp. 27–
36.

[Kar72]

R. M. Karp. “Reducibility among combinatorial problems”. Complexity of
Computer Computations (12/1972). Ed. by R. E. Miller and J. W. Thatcher,
pp. 85–103.

[Lam12]

M. Lampis. “Improved Inapproximability for TSP”. Proceedings 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012. Vol. 7408. Lecture Notes in Computer Science. Springer Berlin
Heidelberg, 2012, pp. 243–253.

[Man08]

B. Manthey. “On Approximating Restricted Cycle Covers”. en. SIAM Journal
on Computing 38.1 (01/2008), pp. 181–206.

[MS11]

T. Mömke and O. Svensson. “Approximating Graphic TSP by Matchings”.
Proceedings 52nd IEEE Annual Symposium on Foundations of Computer Science. IEEE, 10/2011, pp. 560–569.

[Muc12]

M. Mucha. “13/9-Approximation for Graphic TSP”. Theory of Computing
Systems 55.4 (12/2012), pp. 640–657.

[PY93]

C. H. Papadimitriou and M. Yannakakis. “The Traveling Salesman Problem
with Distances One and Two”. en. Mathematics of Operations Research 18.1
(02/1993), pp. 1–11.

[SG76]

S. Sahni and T. Gonzalez. “P-Complete Approximation Problems”. Journal
of the ACM 23.3 (07/1976), pp. 555–565.

[SV14]

A. Sebő and J. 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 (11/2014), pp. 597–629.

26

