This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

Edge Elimination in TSP Instances
Stefan Hougardy and Rasmus T. Schroeder

arXiv:1402.7301v1 [cs.DM] 28 Feb 2014

Research Institute for Discrete Mathematics, University of Bonn

Abstract. The Traveling Salesman Problem is one of the best studied
NP-hard problems in combinatorial optimization. Powerful methods havebeen developed over the last 60 years to find optimum solutions to large
TSP instances. The largest TSP instance so far that has been solved
optimally has 85,900 vertices. Its solution required more than 136 years of
total CPU time using the branch-and-cut based Concorde TSP code [1].
In this paper we present graph theoretic results that allow to prove thatsome edges of a TSP instance cannot occur in any optimum TSP tour.
Based on these results we propose a combinatorial algorithm to identify
such edges. The runtime of the main part of our algorithm is O(n2 log n)
for an n-vertex TSP instance. By combining our approach with the Concorde TSP solver we are able to solve a large TSPLIB instance morethan 11 times faster than Concorde alone.
Keywords: traveling salesman problem, exact algorithm

1

Introduction

An instance of the Traveling Salesman Problem (TSP for short) consists of acomplete graph on a vertex set V together with a symmetric length functionl : V ×V → R+ . A tour T is a cycle that contains each vertex of the
P graph exactly
once. The length of a tour T with edge set E(T ) is defined as e∈E(T ) l(e). A
tour T for a TSP instance is called optimum if no other tour for this instancehas smaller length. Finding such an optimum TSP tour is a well known NP-hardproblem [5].
The Traveling Salesman Problem is one of the best studied problems in combinatorial optimization. Many exact and approximate algorithms have been developed over the last 60 years. In this paper we present several theoretical results that allow us to eliminate edges from a TSP instance that provably cannot
be contained in any optimum TSP tour. Based on these results we present a
combinatorial algorithm that identifies such edges. As the runtime of our mainalgorithm is only O(n2 log n) for an n-vertex instance, it can be used as a preprocessing step to other TSP algorithms. On large instances our algorithm canspeed up the runtime of existing exact TSP algorithms significantly. It also can
improve the performance of heuristic algorithms for the TSP. We present examples for both applications in Section 7. For a good description of the state of theart in algorithms for the Traveling Salesman Problem see [1].
Our results are motivated by studying 2-dimensional Euclidean TSP instances, i.e., instances where the vertices are points in the Euclidean plane andThis paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

2

the length of an edge is the Euclidean distance between the two corresponding
points. However, most of our results hold for arbitrary symmetric TSP instancesthat even do not need to be metric.
Our Contribution. We present several results that allow to prove that certain
edges in a TSP instance cannot belong to any optimum TSP tour. Our Main Edge
Elimination Theorem that we prove in Section 3 turns out to be quite powerful.
It allows to reduce the n(n − 1)/2 edges of an n-vertex TSP instance to about
30n edges or less for the TSPLIB [9] instances. Some additional methods foreliminating edges are presented in Section 4. We combine these with a backtrack
search which we present in Section 6. This will allow us to reduce the numberof edges in the TSPLIB instances to about 5n edges.
Unfortunately, our Main Edge Elimination Theorem does not directly leadto an efficient algorithm for eliminating edges in a TSP instance. Thus, a second
major contribution of this paper is contained in Section 5 where we prove that aweaker form of our Main Edge Elimination Theorem can be checked in constanttime per edge. This allows to apply our methods to very large TSP instances
containing 100,000 or more vertices. The total runtime on such a large instance isless than three days on a single processor. Our algorithm can be run in parallelon all edges resulting in a runtime of less than a minute if sufficiently many
processors are available.
Section 7 contains the results of our algorithm on TSPLIB [9] instances aswell as on a 100,000 vertex instance. Here we also show how our approach can
speed up finding optimum solutions to large TSP instances significantly. The
TSP solver Concorde [1] is the fastest available algorithm to solve large TSP
instances optimally. Concorde needs more than 199 CPU days for the TSPLIB
instance d2103. After running our edge elimination algorithm for 2 CPU days
the runtime of Concorde decreases to slightly more than 16 CPU days. The total
speed up we obtain is more than a factor of 11.
We also report two other successful applications of the edge elimination approach in Section 7.

2

Notation and Preliminaries

To avoid some degenerate cases we assume in this paper that a TSP instancecontains at least four vertices. Edges that do not belong to any optimum TSP
tour will be called useless. We extend the definition of a TSP instance to instances (V, E) together with a length function l : E → R+ where E contains alledges of the complete graph on V except some useless edges. This implies that
all optimum TSP tours on the complete graph on V are contained in the graph(V, E). Therefore, to find an optimum TSP tour it suffices to consider edges fromE. However, to prove that some edge in E is useless it might be useful to also
look at edges that are not in E. Our edge elimination algorithm will start withsome TSP instance (V, E) and return an instance (V, E ′ ) such that E ′ is a subsetof E and contains all optimum TSP tours.

This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

3

As most of our results are inspired by studying Euclidean instances we willoften call a vertex in a TSP instance a point. If x and y are two vertices in a
TSP instance we will denote the edge {x, y} by xy simply.
A TSP instance is called metric if l(xy) ≤ l(xz) + l(zy) for all vertices
x, y, z ∈ V . Our results do not require that the TSP instance is metric. However,
we can improve some of our results if we assume some metric properties of theinstance. Euclidean TSP instances are of course metric, but because of problems
with floating point accuracy such instances are usually not considered in practice.
The well known TSPLIB [9] instances for example use the discretized Euclidean
distances EUC 2D and CEIL 2D. In the first, the Euclidean distance is rounded
to the nearest integer while in the second it is rounded up to the next integer.
Note that the EUC 2D distance function is not metric and that an optimum
TSP tour for such an instance may contain two crossing edges.
Currently, the most successful heuristic TSP algorithms [7] are based on theconcept of k-opt moves. Given a TSP tour a k-opt move makes local changes tothe tour by replacing k edges of the tour by k other edges. For a k-opt move
we require, that after the replacement of the k edges the new subgraph is 2regular. If the new subgraph is again a tour we call the k-opt move valid. If a
tour T allows a valid k-opt move resulting in a shorter tour, then T cannot be an
optimum tour. This simple observation is the core of our algorithm for proving
the existence of useless edges.
Let pq and xy be two edges in a TSP instance. We call pq and xy compatible,
denoted by pq ∼ xy, if
max (l(px) + l(qy), l(py) + l(qx)) ≥ l(pq) + l(xy) .

(1)

Otherwise pq and xy are called incompatible. Note that two edges that have atleast one vertex in common are always compatible.
Lemma 1. Any two edges in an optimum TSP tour are compatible.
Proof. Assume pq and xy are two incompatible edges in an optimum TSP tour
T . By (1) we have l(px)+l(qy) < l(pq)+l(xy) and l(py)+l(qx) < l(pq)+l(xy).
Thus T can be improved by a 2-opt move, that replaces edges pq and xy by either
px and qy or by py and qx. One of these two 2-opt moves must be valid. This
contradicts the assumption that T is an optimum TSP tour.
⊔⊓
For k > 2 we call a set of k edges k-incompatible, if they cannot belong to
the same optimum TSP tour.

3

The Main Edge Elimination Theorem

To be able to formulate our Main Edge Elimination Theorem, we need to introduce the concept of potential points first. Let (V, E) be a TSP instance andpq ∈ E. For r ∈ V \ {p, q} define
R := {x ∈ V | rx ∈ E ∧ pq ∼ rx} .

(2)This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

4Let R1 , R2 ⊂ V and R ⊂ R1 ∪ R2 . We call r potential with respect to pq
and R1 and R2 , if for every optimum tour containing pq, the two neighbors of
r cannot both lie in R1 respectively R2 . We say that such a covering certifies
the potentiality of r. Note that R1 ∩ R2 needs not to be empty. However if r
is potential, in any optimum tour containing pq, r cannot be connected with
R1 ∩ R2 . In Section 5 we will develop efficient methods for certifying potential
points.
Theorem 1 (Main Edge Elimination Theorem). Let (V, E) be a TSP instance and pq ∈ E. Let r and s be two different potential points with respect to pq
with covering R1 and R2 respectively S1 and S2 . Let r 6∈ S1 ∪S2 and s 6∈ R1 ∪R2 .
Ifl(pq) − l(rs) + min {l(sz) − l(pz)} + min {l(ry) − l(qy)} > 0
(3)
z∈S1

y∈R2

and
l(pq) − l(rs) + min {l(rx) − l(px)} + min {l(sw) − l(qw)} > 0 ,
x∈R1

(4)

w∈S2

then the edge pq is useless.
Proof. Assume that the edge pq is contained in an optimum TSP tour T . Letrx, ry, sz, sw ∈ T be the incident edges of r and s. We may assume that thevertices x, y, z, and w are labeled in such a way that x ∈ R1 , y ∈ R2 , z ∈ S1 ,and w ∈ S2 . As r and s are potential, we have r, s 6∈ {p, q}. By assumption we
have rs 6∈ T , making the four edges rx, ry, sz and sw distinct.
y

x
r

p

q

r

p

s
z

y

x

q

r

p

s
w

The situation of Theorem 1.

z

y

x

q

s
w

One possible 3-opt.

zw

Another possible 3-opt.

Fig. 1. Two possible 3-opt moves that imply that the edge pq is useless.

Now there exist two possible 3-opt moves as shown in Figure 1. The first is
to replace pq, rx, and sw with px, rs, and qw. The second is to replace pq, ry,
and sz with pz, rs, and qy. It is easy to verify that for every tour containing theegdes pq, rx, ry, sz and sw, one of these two 3-opt moves must be valid.
The two 3-opt moves are decreasing the length of the tour T byl(pq) − l(rs) + l(rx) − l(px) + l(sw) − l(qw) respectivelyl(pq) − l(rs) + l(ry) − l(py) + l(sz) − l(qz) .

(5)
(6)

By inequalities (3) and (4), both terms are strictly positive. Since one of these 3opt moves is valid, this yields a tour shorter than T , contradicting the optimalityof T .
⊔⊓

This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

54The Close Point Elimination Theorems

The Main Edge Elimination Theorem will be our primary tool to prove that anedge in a TSP instance is useless. As soon as many edges of a TSP instance are
known to be useless other methods can be applied. In this section we present
our so called Close Point Elimination. When applied to the complete graph ofa TSP instance it will eliminate almost no edge. However, in combination with
the Main Edge Elimination Theorem it will allow to identify additional uselessedges.
Theorem 2 (Close Point Elimination Theorem). Let (V, E) be a TSP instance and pq ∈ E. Let r ∈ V \{p, q} and define R := {x ∈ V | rx ∈ E ∧ pq ∼ rx}.
If for all x, y ∈ R with {x, y} 6= {p, q} we havel(xy) + l(pr) + l(qr) < l(pq) + l(xr) + l(yr)(7)

then the edge pq is useless.
Proof. Assume that an optimum tour T contains the edge pq. Let xr and ry be
the two edges in T that are incident with r. Then {x, y} 6= {p, q} and x and ymust be in R. By assumption inequality (7) holds. Then we can replace the edges
pq, xr, and yr with xy, pr, and qr and obtain a tour that is shorter than T . Notethat this also holds if one of x and y equals one of p and q. This contradicts the
optimality of the tour T .
⊔⊓For the degenerate case with x = p we show a stronger result by making useof the notion of metric excess. It will allow us to short cut a eulerian subgraphin an instance that needs not to be metric. The metric excess mpq (z) of a vertex
z with respect to an edge pq is defined asminx,y∈N (z)\{p,q}max { l(xz) + l(zp) − l(xp), l(yz) + l(zp) − l(yp),l(xz) + l(zq) − l(xq), l(yz) + l(zq) − l(yq) } .

Theorem 3 (Strong Close Point Elimination Theorem). Let pq, pr andrx be three edges of a TSP instance (V, E). Let z ∈ V \ {p, q, r, x}. Ifl(xq) + l(rz) + l(zp) − mpr (z) < l(pq) + l(rx) ,(8)then the edges pq, pr and rx are 3-incompatible.
Proof. Assume that an optimum tour T contains the edges pq, pr and rx. We
show that there exists a 3-opt move yielding a tour shorter than T . Delete theedges pq and rx and insert the edges qx, pz and rz. Note that this edge set is
eulerian but not a TSP tour as vertex z has degree four. But as l(xq) + l(rz) +l(zp) − mpr (z) < l(pq) + l(rx) a short cut is possible that yields a tour shorter
than T . This contradicts the optimality of the tour T .
⊔⊓This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

6

5

Certifying potential points

Starting with a complete graph, it can be very inefficient, to exclude edges using the criteria discussed so far. We will show how to adopt the Main Edge
Elimination Theorem such that most edges can be excluded efficiently.
The aim of this section is to show that one can prove in constant time thata point r is potential with respect to an edge pq. To be able to do so, we willassume in the following that the distance function l is the EUC 2D function.
Similar results hold for any other distance function that is close to the Euclidean
distance. By |pq| we denote the Euclidean distance of p and q. Note thatl(pq) −

1
1
≤ |pq| ≤ l(pq) + .
2
2

(9)

We now want to find a covering for a point r and an edge pq. We will therefore
take a closer look at the set R := {x ∈ V | rx ∈ E ∧ pq ∼ rx} which was alreadydefined in Section 3. Observe that in a metric space the compatibility of the edges
pq and rs implies that the edges pq and rt are also compatible for all t ∈ rs.
Since we use EUC 2D lengths, this only holds after adding some constants. For
each point r choose δr s.t. no vertex apart from r lies in the interior of the circle
around r with radius δr . One can for example use
δr :=1+ max{d ∈ Z+ | ∀s ∈ V \ {r} l(rs) > d} .
2

(10)

For an edge pq and a point r ∈ V \ {p, q} define the two lengths
lp := δr + l(pq) − l(qr) − 1 and lq := δr + l(pq) − l(pr) − 1 .

(11)For each point s ∈ V \ {r} define sr ∈ rs such that |rsr | = δr .
Lemma 2. Let (V, E) be a TSP instance, pq ∈ E, r ∈ V \{p, q} and s ∈ V \{r}.
If |psr | < lp and |qsr | < lq then the edges pq and rs are incompatible.
Proof. We show that both 2-opt moves involving the edges pq and rs have shorter
length. Using (9), (11), and the triangle inequality we get:11
+ l(qr) < lp + |ssr | + + l(qr)221= δr + l(pq) − l(qr) − + |ssr | + l(qr) ≤ l(pq) + l(rs)2

l(ps) + l(qr) ≤ |psr | + |ssr | +l(qs) + l(pr) < l(pq) + l(rs) is proven analogously. Hence pq and rs are incompatible.
⊔⊓
Figure 2 illustrates Lemma 2. It shows two cones Rp and Rq for which R ⊂Rp ∪Rq . The cones are defined as Rp := {t | |qtr | ≥ lq } and Rq := {t | |ptr | ≥ lp }.
We do not need that the cones Rp and Rq are disjoint. However we need thatthey actually exist, i.e. the circles around p and q have to intersect the circle
around r.

This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

7

Rp

q

r

p

Rq
Fig. 2. The small dots indicate all possible endpoints for the edge rs such that rs ∼ pq.
By Lemma 2 all these vertices must be contained in the gray cones Rp and Rq .

Lemma 3. Let (V, E) be a TSP instance, pq ∈ E and r ∈ V \ {p, q}. If
lp + lq ≥ l(pq) −

1
,
2

(12)

then the circle with center r and radius δr intersects both circles with centers p
and q and radii lp respectively lq .
Proof. It suffices to show |ir| − δr ≤ li ≤ |ir| + δr for i ∈ {p, q}.
(12)
1
1
(11)
− δr = l(pq) − − lq ≤ lp
2
2
(11)
1
1
≤ (|pr| + |qr| + ) − (|qr| − ) + δr − 1 = |pr| + δr
2
2

|pr| − δr ≤ l(pr) +Analogously for i = q.

⊔⊓

A naive way to prove that Rp and Rq certify the potentiality of r is to lookat all possible 3-opt moves.
Lemma 4. Let (V, E) be a TSP instance and pq ∈ E. For r ∈ V \ {p, q} let
R ⊂ Rp ∪ Rq with R = {x ∈ V | rx ∈ E ∧ pq ∼ rx}. If for i ∈ {p, q}:l(pq) + l(rx) + l(ry) > l(pr) + l(rq) + l(xy)for all x, y ∈ Ri ,(13)then Rp and Rq certify the potentiality of r.
Proof. Assume that pq is contained in an optimum tour T and rx, ry ∈ T withx, y ∈ Ri for i ∈ {p, q}. Then replacing the edges pq, rx and ry by the edges
pr, rq and xy is a valid 3-opt move. By inequality (13) this 3-opt move yields a
shorter tour, contradicting the optimality of T .
⊔⊓This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

8Lemma 4 yields a method to check in O(n2 ) time that a vertex r is potential.
We now want to show that the potentiality of a vertex r can be certified inconstant time. We assume that the edge pq is part of an optimum tour T .
Furthermore we consider the covering Rp and Rq as described above. The anglesof the cones Rp and Rq are denoted by αp respectively αq . The certification
follows from a simple argument.
Lemma 5. Assume that pq is contained in an optimum TSP tour T , r ∈ V \{p, q} and the angle γ between the two edges incident with r in T satisfies
γ > max{αp , αq } .

(14)Then the neighbors of r in T cannot both lie in Rp respectively Rq .
Proof. W.l.o.g. assume both neighbors of r in T lie in Rp . This immediatly
implies γ ≤ αp , contradicting (14).
⊔⊓
It now suffices to show that inequality (14) holds for every optimum tour
containing pq. This can be checked using the following statement.
Lemma 6. Let (V, E) be a TSP instance and T an optimum tour. Let pq ∈ T
and r ∈ V \ {p, q}. Assume that inequality (12) holds. Define the angle γr as
2 !
lp + lq − l(pq) + 12
γr := arccos 1 −
.
(15)
2δr2
Then the angle γ between the two edges of T incident with vertex r satisfiesγ ≥ γr .

(16)

Proof. Let rx, ry ∈ T be the two incident edges of r. Let µ := |xr yr | . The cosine
formula yields the following equation:µ2 = 2δr2 − 2δr2 cos γ(17)

As T is an optimum tour, there is no valid 3-opt move which yields a shorter
tour. Hence we get:

⇒
⇒
(12)

⇒

⇒
⇒

l(pq) + l(rx) + l(ry) ≤ l(pr) + l(qr) + l(xy)lp + lq + |xr x| + |yr y| − l(pq) + 1 ≤ l(xy)1
lp + lq − l(pq) + ≤ µ2
2
1
lp + lq − l(pq) +≤ µ2 = 2δr2 − 2δr2 cos γ
2

lp + lq − l(pq) + 21
cos γ ≤ 1 −2δr2γ ≥ γr .

2⊔⊓

This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

9

From Lemma 5 and Lemma 6 we immediately get the following result.
Lemma 7. Let pq be an edge contained in some optimum TSP tour T andr ∈ V \ {p, q}. Assume that inequality (12) holds. If
γr > max{αp , αq } ,(18)then the sets Rp and Rq certify the potentiality of r.
It is easy to see that the angles αp and αq can be computed in constant time.
Details are given in the appendix.
The results so far provide a way to prove in constant time that a given
vertex is potential. Notice that not all potential points can be detected using
this approach. However, as we will see in Section 7, sufficiently many potential
points can be detected using this method. For simplifying notation we introduce
the following concept: Let pq be an edge and r ∈ V \ {p, q}. The vertex r is calledstrongly potential (with respect to pq), if the conditions (12) and (18) hold.
Thus, checking whether a point r is strongly potential can be done in constant time (assuming that the value δr is known, which can be computed in a
preprocessing step for all vertices). Verifying the inequalities in the Main Edge
Elimination Theorem still needs O(n) time. The aim now is to show that thiscan be done in constant time by computing appropriate lower bounds for (3)and (4).
Lemma 8. Let (V, E) be a TSP instance and r strongly potential with respect
to pq. Let Rp and Rq be the covering certifying r. Thenmin {l(rx) − l(px)} ≥ δr − 1 − max{|pxr | : x ∈ Rp } and(19)

min {l(ry) − l(qy)} ≥ δr − 1 − max{|qyr | : y ∈ Rq } .

(20)

x∈Rp

y∈Rq

Proof. Let x ∈ Rp . Thenl(rx) − l(px) ≥ |rx| − |px| − 1 ≥ δr + |xr x| − (|pxr | + |xr x|) − 1≥ δr − 1 − max{|pxr | : x ∈ Rp }Similarly one can prove this for the set Rq .

⊔⊓Let Cr be the circle around r with radius δr . Define the two arcs
Bp := {x ∈ Cr | |qx| ≥ lq } and Bq := {y ∈ Cr | |py| ≥ lp } .
Further let p̃ and q̃ be the points on Cr with greatest distance to p respectively
q. Since Bp and Bq are connected, the maxima in the inequalities (19) and (20)can only be attained at p̃ respectively q̃, or at the endpoints of Bp respectively
Bq . We consider the case that|pq̃| ≤ lp

and |q p̃| ≤ lq .

(21)This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

10This gives thatmax{|pxr | : x ∈ Rp } ≤ max{t | t ∈ Bp } and(22)

max{|qyr | : y ∈ Rq } ≤ max{t | t ∈ Bq } ,(23)where the right hand sides can easily be calculated in constant time. Details are
given in the appendix.

6

The Algorithm

In this section we describe our algorithm that eliminates useless edges. It consistsof three independent steps. Step 1 uses the results of Section 3 and Section 5 andeliminates the majority of all edges. Step 2 applies the Main Edge Eliminationin combination with the Close Point Elimination to eliminate additional edges.
Finally in Step 3 we use a backtrack search of bounded depth to eliminate evenmore edges.
Step 1: Fast Elimination To prove that an edge pq is useless we need tofind two potential points r and s satisfying the conditions of the Main Edge
Elimination Theorem. For a point r we use the method described in Section 5,
to prove that it is potential. In fact we will only use r if it is strongly potential.
This can be checked in constant time. The next step is to calculate the minima
appearing in the Main Edge Elimination Theorem using Lemma 8. This can bedone separately for each potential point in constant time.
Once two potential points r and s with their corresponding minima are calculated, one can check in constant time whether the inequalities of the Main
Edge Elimination Theorem are satisfied. Since only two potential points which
satisfy the conditions of the theorem are needed, a smart ordering and stopping
criteron for checking the potentiality of points can speed up the algorithm drastically. We select the points ordered by their distance from the midpoint of theedge pq and stop after at most 10 points that have been considered.
Using a 2-d tree [2] we compute in a preprocessing step the values δr for all
vertices of the instance. In most cases it turns out that at most three strongly
potential points have to be considered to prove that an edge is useless.
Step 2: Direct Elimination For an edge pq we consider two vertices r and swith all their incident edge pairs. The Close Point Elimination is used to reduce
the number of possible edge pairs. The edge pq can be eliminated either if noedge pair can be found for r or s, or if all combinations of edge pairs satisfy thecondition of the Main Edge Elimination Theorem.
Step 3: Backtrack Search In this step starting with an edge pq we extend
a set of disjoint paths recursively. We allow two operations for the extension.
Either we select one of the existing paths and add an edge incident to one ofThis paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

11

its endpoints. Or we add a vertex not yet contained in any of the disjoint paths
and two edges incident with this vertex. After each extension we check whether
the Main Edge Elimination Theorem or the Close Point Elimination allows toeliminate one of the path edges. In this case we backtrack. Moreover we checkthat the collection of paths is minimal in the sense that no collection of paths
exists that has shorter length and that connects the same pairs of endpoints
and uses the same set of interior points. We use an extension of the Held-Karpalgorithm [6] for this. We always select the extension of the set of paths thathas the smallest number of possibilities. If all extensions have been examined
without reaching a predefined extension depth, then we have proven that edge
pq is useless.

7

Results

We applied our algorithm to all TSPLIB [9] instances which use the EUC 2D
metric as well as to some larger EUC 2D instances from [3]. Table 1 contains
the results on some of these instances.
Table 1. Results for some TSPLIB instances with at least 1,000 vertices as well as a
100,000 vertex instance from [3]. The first three columns contain the instance name,the number of vertices and the number of edges. Then for each of the three steps
as described in Section 6 we list the number of edges that remain after this step
as well as the runtime. For Step 3 we used an extension depth of 10 which gave areasonable trade off between the runtime and the number of eliminated edges. The lasttwo columns contain the total runtime of our algorithm and the ratio of the number ofedges remaining after Step 3 divided by the number of vertices. All runtimes are givenin the format hh:mm:ss and are measured on a single core of a 2.9GHz Intel Xeon.

Step 1
Step 2
Step 3
total ratio
edges
time edges
time edges
time runtime
pr10021002
501501
42636
1
5810
2:13
4521 2:28:07 2:30:21 4.2
u1060
1060
561270
43887
1
6063
2:24
4619 3:30:48 3:33:13 4.4
vm10841084
586986
40958
1
6035
3:28
4610 1:17:35 1:21:05 4.3
pcb11731173
687378
32533
1
7662
33
6084 3:10:17 3:10:51 5.2
d1291
1291
832695 122897
4 12552
52:21 11317 13:33:14 14:25:40 8.8
rl13041304
849556 124561
3 21689
11:54 14527 12:53:14 13:05:11 11.1
rl13231323
874503 106860
2 16743
5:33 12691 9:41:18 9:46:53 9.6
nrw13791379
950131
28468
1
7199
1:58
5752 2:12:44 2:14:44 4.2
u1432
1432
1024596
21970
1
7817
2:51
6495 2:13:02 2:15:55 4.5
d1655
1655
1368685 230855
9 14345
37:30 12103 10:05:46 10:43:26 7.3
vm17481748
1526878 144681
6 12303
23:10
7691 2:48:14 3:11:30 4.4
u1817
1817
1649836 109056
5 13201
10:58 11736 6:19:22 6:30:25 6.5
rl18891889
1783216 206768
9 23410 3:15:40 18673 25:18:52 28:34:41 9.9
d2103
2103
2210253 166866
8 19631
55:01 18105 18:19:34 19:14:44 8.6
u2152
2152
2314476 117030
5 15101
11:17 13170 7:07:45 7:19:08 6.1
u2319
2319
2687721
21698
3
9919
44
9473 1:41:41 1:42:22 4.1
pr23922392
2859636 121514
7 15598
13:03 12088 7:41:45 7:44:55 5.1
pcb30383038
461320395576
8 17940
11:05 14869 5:44:08 5:55:22 4.9
fnl44614461
9948030 128527
15 23963
9:30 19082 7:14:21 7:24:07 4.3
brd14051
14051
98708275 2661869
4:39 93497 18:50:15 64486 28:39:22 47:34:16 4.6
d1511215112 114178716 1703765
5:51 130110 10:25:44 66010 38:37:42 49:09:17 4.4
d18512
18512 171337816 1449877
5:30 112681 1:49:35 84203 32:38:07 34:33:13 4.5
mona-lisa100k 100000 4999950000 2071297 3:45:21 476001
22:51 322716 55:42:51 59:51:04 3.2
instancenmThis paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

12

The TSP solver Concorde [1] is the fastest available algorithm to solve large
TSP instances optimally. It can be downloaded at [3]. We applied Concordeto the TSPLIB instance d2103. The total runtime needed by Concorde was17, 219, 190 seconds1 . This agrees with the runtime reported for this instance on
page 503 of [1]. Then we ran the three steps of our algorithm as described in
Section 6. For Step 3 we used an extension depth of 12. After 168, 153 seconds
all but 16, 566 edges were eliminated. We changed the length of all eliminatededges to some large value and gave this new instance again to Concorde. On
this instance Concorde needed 1, 392, 582 seconds. Thus the total runtime was
improved by our edge elimination algorithm by more than a factor of 11.
Two other successful applications of our edge elimination approach were reported to us by Cook [4]. First, the edge elimination approach in combination with the LKH algorithm [7] improved the so far best known TSP tour for
the DIMACS instance E100k.0 [8]. The shortest tour known so far had length
225, 786, 982. It was found using the LKH algorithm. Cook’s implementationof an edge elimination approach eliminated all but 274, 741 edges in the TSP
instance E100k.0. By applying the LKH algorithm to this edge set a tour oflength 225, 784, 127 was found [8]. Secondly, Cook applied the edge elimination
approach to a truly Euclidean instance (i.e., a Euclidean instance where thepoint distances are not rounded). Finding optimum TSP tours in such instances
is much harder than in instances with rounded Euclidean norm. The largest truly
Euclidean instance that Cook was able to solve so far had 500 points. With thehelp of the edge elimination approach he solved an instance with 1000 points.

References
1. D.L.Applegate, R.E.Bixby, V.Chvátal, W.J.Cook. The Traveling Salesman Problem.
A Computational Study. Princeton University Press, 2006
2. J.L.Bently. Multidimensional binary search trees used for associative searching.
Communications of the ACM, Volume 18, Number 9 (September 1975), pp. 509–517
3. W.J.Cook’s TSP website at http://www.math.uwaterloo.ca/tsp/
4. W.J.Cook, personal communication, December 2013.
5. M.R.Garey, D.S.Johnson. Computers and Intractability. Freeman, New York 1979
6. M.Held, R.M.Karp A Dynamic Programming Approach to Sequencing Problems.
Journal of the Society for Industrial and Applied Mathematics, Vol. 10, No. 1(Mar.,1962), pp. 196-210
7. K.Helsgaun. General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, Volume 1, Issue 2-3 (2009), pp. 119–163
8. K.Helsgaun, http://www.akira.ruc.dk/˜keld/research/LKH/DIMACS results.html
9. G.Reinelt. TSPLIB 95. Interdisziplinäres Zentrum für Wissenschaftliches Rechnen(IWR), Heidelberg, 1995

1

Runtime on a 2.9GHz Intel Xeon using Concorde [3]. We observed that the runtime
of Concorde can vary by more than 40% on the same instance. Therefore, we took
the average runtime of two independent runs. The Concorde log-files for all runs canbe found at http://www.or.uni-bonn.de/~hougardy/EdgeElimination.

This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

13

8

Appendix

8.1

The angles αp and αq

The following lemma shows how to compute the angles αp and αq , discussed in
Section 5.
Lemma 9. Let (V, E) be TSP instance, pq ∈ E and r ∈ V \ {p, q}. Then theangles αp and αq of the cones Rp respectively Rq satisfy!
lq2 − δr2 − |rq|2
respectively(24)
αp = 2 · arccos
2δr |rq|!
lp2 − δr2 − |rp|2
αq = 2 · arccos.
(25)2δr |rp|
Proof. Let Cr be the circle around r with radius δr and Cq the circle around q
with radius lq . Let t be one intersection point of these two circles. Consider the
triangle with the points q, r and t. Let ωq be the angle of the triangle at the
point r. The cosine theorem then yields
δr2 + |rq|2 − 2δr |rq| cos(ωq ) = lq2 .

(26)

Hence we can conclude
cos

α 
p

2

= cos (180◦ − ωq )(27)

= − cos(ωq )

(28)

2
2
2
(26) lq − δr − |rq|=2δr |rq|.

(29)

This equation implies (24). Equation (25) can be shown equivalently.
8.2

Validating

In order to calculate the maxima of (19) and (20), we need to define some angles.
For an edge pq ∈ E and a point r ∈ V \ {p, q} we define εp and εq as the angles inthe triangle pqr at the points p respectively q. Further let t be such that |rt| = δr
and |pt| = lp . Let θp be the angle in the triangle prt at the point p. The angle θq
is defined equivalently. By the cosine theorem we obtain the following equations:|pq|2 + |pr|2 − |qr|2
2|pq||pr|2|pq| + |qr|2 − |pr|2
cos εq =2|pq||qr|2
lp + |pr|2 − δr2cos θp =2lp |pr|cos εp =cos θq =lq2 + |qr|2 − δr2.
2lq |qr|

(30)
(31)
(32)
(33)

This paper appeared in: Graph-Theoretic Concepts in Computer Science, WG 2014, D.Kratsch, I.Todinca (Eds.), LNCS 8747, Springer 2014, 275-286

14

δ
r
θq
εq

p

q

Fig. 3. The angles ε and θ

By considering the cosine theorem in the triangles pq p̃ respectively pq q̃, theinequalities (21) are equivalent to(|qr| + δr )2 + |pq|2 − lp2≤ cos εq2(|qr| + δr )|pq|(|pr| + δr )2 + |pq|2 − lq2≤ cos εp .
2(|pr| + δr )|pq|

(34)
(35)

We want to calculate the maxima of Lemma 8. They correspond tomax{|psr | : s ∈ Rp } = max{bp , b′p }(36)max{|qsr | : s ∈ Rq } = max{bq , b′p } ,(37)whereas the endpoints of the archs Bp and Bq are defined as bp and b′p respectively bq and b′q .
Lemma 10. Assuming ε ≤ 180◦ and θ ≤ 180◦ then we have the following
equivalence:
ε + θ ≤ 180◦ ⇔ cos ε + cos θ ≥ 0(38)
Using simple geometric calculations, we can deduce the following lemma:
Lemma 11. Let r be strongly potential with respect to pq, and let the inequalities (21) hold. Let εp + θp ≤ 180◦ and εq + θq ≤ 180◦ . Then(max{|psr | : s ∈ Rp })2 = |pq|2 + lq2 − 2|pq|lq cos(εq + θq )2(max{|qsr | : s ∈ Rq }) = |pq|2

+ lp2 − 2|pq|lp cos(εp + θp )

(39)
(40)

Proof. From the assumption we can follow cos(εq −θq ) ≥ cos(εq +θq ). The cosine
theorem then implies2(max{|psr | : s ∈ Rp }) = |pq|2 + lq2 − 2|pq|lq cos(εq + θq ) .
⊔⊓