A LINEAR TIME ALGORITHM FOR THE 3-NEIGHBOUR TRAVELLING
SALESMAN PROBLEM ON A HALIN GRAPH AND EXTENSIONS

arXiv:1504.02151v5 [cs.DM] 4 Sep 2017

BRAD WOODS, ABRAHAM PUNNEN, AND TAMON STEPHEN
Abstract. The Quadratic Travelling Salesman Problem (QTSP) is to find a least cost Hamiltonian cycle
in an edge-weighted graph, where costs are defined for all pairs of edges contained in the Hamiltonian cycle.
The problem is shown to be strongly NP-hard on a Halin graph. We also consider a variation of the QTSP,
called the k-neighbour TSP (TSP(k)). Two edges e and f , e 6= f , are k-neighbours on a tour τ if and only
if a shortest path (with respect to the number of edges) between e and f along τ and containing both e
and f , has exactly k edges, for k ≥ 2. In (TSP(k)), a fixed nonzero cost is considered for a pair of distinct
edges in the cost of a tour τ only when the edges are p-neighbours on τ for 2 ≤ p ≤ k. We give a linear time
algorithm to solve TSP(k) on a Halin graph for k = 3, extending existing algorithms for the cases k = 1, 2.
Our algorithm can be extended further to solve TSP(k) in polynomial time on a Halin graph with n nodes
when k = O(log n). The possibility of extending our results to some fully reducible class of graphs is also
discussed. TSP(k) can be used to model the Permuted Variable Length Markov Model in bioinformatics as
well as an optimal routing problem for unmanned aerial vehicles (UAVs).

1. Introduction
The Travelling Salesman Problem (TSP) is to find a least cost Hamiltonian cycle in an edge weighted
graph. It is one of the most widely studied combinatorial optimization problems and is well-known to be
NP-hard. The TSP model has been used in a wide variety of applications. For details we refer the reader to
the well-known books [2, 8, 18, 23, 27] as well as the papers [4, 13, 21, 22].
For some applications, more than linear combinations of distances between consecutive nodes are desirable in formulating an objective function. Consider the problem of determining an optimal routing of an
unmanned aerial vehicle (UAV) which has a list of targets at specific locations. This can be modelled as a
TSP which requires a tour that minimizes the distance travelled. However, such a model neglects to take
into account the physical limitations of the vehicle, such as turn radius or momentum. To illustrate this
idea, in Figure 1 we give a Hamiltonian path, in Figure 2 we give the corresponding flight path, and Figure 3
shows a route which is longer but can be travelled at a greater speed and hence reducing the overall travel
time. To model the traversal time, we can introduce penalties for pairs of (not necessarily adjacent) edges
to force a smooth curve for its traversal. In this paper we consider a generalization of the TSP which can
be used to model similar situations and contains many variations of the TSP, such as the angular-metric
TSP [1] and the TSP [5] as special cases.
Let G = (V, E) be an undirected graph on the node set V = {0, 1, . . . , n − 1} with the convention that
all indices used hereafter are taken modulo n. For each edge (i, j) ∈ E a nonnegative cost cij is given. Let
F be the set of all tours (Hamiltonian cycles) in G and let τ = (v0 , v1 , . . . , vn−1 , v0 ) ∈ F. Note that a tour
τ can be represented either by its sequence (permutation) of the vertices, or by the sequence, or simply the
set, of edges it traverses. In this paper, it is usually more convenient to work with the edge representation.
The edges e = (vi , vi+1 ) and f = (vj , vj+1 ), e 6= f , are k-neighbours on τ , if and only if a shortest path
between e and f on τ containing these edges has exactly k edges, for k ≥ 2. Here the shortest path refers to
the path with the least number of edges, rather than the minimum cost path. Thus e and f are 2-neighbours
in τ if and only if they share a common node in τ .
Let q(e, f ) be the cost of the pair (e, f ) of edges and δ(k, τ ) = {(e, f ) : e, f ∈ τ and e and f are pneighbours on τ for some 2 ≤ p ≤ k}. Assume that q(e, f ) = q(f, e) for every pair of edges e, f ∈ E. Then
the k-neighbour TSP (TSP(k)) is defined as in [31]
1

Figure 2. Smoothing of the optimal TSP tour.
Figure 1. Optimal TSP tour.

Figure

Figure
Figure
3. A
Figure 3. A route which
cantour
be
1.
Optimal
Figure
which
can
1. Optimal TSP tour.
TSP
tour
2. Smoothbe
travFigure
2. Smoothing
of the optimal TSP
tour.
with respect
ing of the
elled more
to length.
tour.
quickly.

T SP (k) :

X

Minimize

q(e, f ) +

(e,f )∈δ(k,τ )

Subject to

X

travelled more quickly

c(e)

e∈τ

τ ∈ F.

A closely related problem, the Quadratic TSP (QTSP), is defined as follows:
QT SP :

X

Minimize

(e,f )∈τ ⊗τ

Subject to

q(e, f ) +

X

c(e)

e∈τ

τ ∈ F.

where
τ ⊗ τ = τ × τ \ of
{(e,the
e) : e ∈
τ }. Note: TSP tour.
Figure 2.
Smoothing
optimal
(
Figure 3. A route which
can be iftravelled
more
1 quickly.
δ(n/2, τ )
n is even

gure 3.

τ ⊗τ =

δ((n + 1)/2, τ )

if n is odd.

Thus when k ≥ n/2 (for n even) or k ≥ (n + 1)/2 (for n odd), the k-neighbour TSP reduces to the
Quadratic TSP [33]. Define TSP(1) to be the original TSP. Elsewhere in the literature (e.g. [17], [14]), the
term Quadratic TSP is sometimes used for what we refer to as TSP(2). That is, quadratic terms are allowed,
but only for pairs of edges that share a node.
The bottleneck version of TSP(k) was introduced by Arkin et al. in [3], denoted as the k-neighbour
maximum scatter TSP. Jäger and Molitor [19] encountered TSP(2) while studying the Permuted Variable
Length Markov Model. Several heuristics are proposed and compared in [16, 19] as well as a branch and
bound algorithm for TSP(2) in [16]. A column generation approach to solve TSP(2) is given in [28], lower
bounding procedures discussed in [29], and polyhedral results were reported by Fischer and Helmberg [17],
Fischer [14], and Fischer and Fischer [15]. The k-neighbour TSP is also related to the k-peripatetic salesman
problem [12, 20] and the watchman problem [7]. Algorithms for maximization and minimization versions of
TSP(2) were studied by Staněk [30] and Oswin et al. [26]. To the best of our knowledge, no other works in
the literature address TSP(k).
Referringwhich
to the UAV
discussed earlier,
it isquickly.
clear that the flight subpaths depend on both the
A route
canexample
be travelled
more
angle and distances between successive nodes. By precalculating these and assigning costs to q(e, f ), for
e, f ∈ E, we see that QTSP is a natural model for this problem. In fact, the flight paths may be affected by
edges further downstream. Thus we can get successively better models by considering TSP(1), TSP(2),. . .,

12

TSP(k) in turn. In practice we expect diminishing returns to take hold quickly and hence TSP(k) with small
values of k are of particular interest.
In this paper we show that QTSP is NP-hard even if the costs are restricted to 0-1 values and the
underlying graph is Halin. In contrast, TSP and TSP(2) on a Halin graph can be solved in O(n) time [9, 33].
Interestingly, we show that TSP(3) can also be solved on a Halin graph in O(n) time, although as we move
from TSP(2) to TSP(3), the problem gets much more complicated. In fact, our approach can be extended to
obtain polynomial time algorithms for TSP(k) whenever k = O(log n). We note that while Halin graphs have
treewidth 3, the results on graphs with bounded treewidth (e.g. [6, 11]) usually cannot easily be extended
to optimization problems with quadratic objective functions.
The paper is organized as follows. In Section 2 we introduce some preliminary results and notations for the
problem. The complexity result for QTSP on Halin graphs is given in Section 3. An O(n) algorithm to solve
TSP(3) on Halin graphs is given in Section 4.1, which can be extended to obtain an O(n2(k−1)/2 ) algorithm
for TSP(k). Further extensions of this result to fully reducible classes of graphs are briefly discussed in
Section 5.
An earlier version of the NP-completeness results presented here were included as part of the M.Sc. thesis
of the first author [31].
2. Notations and definitions
A Halin graph H = T ∪ C is obtained by embedding a tree with no nodes of degree two in the plane and
connecting the leaf nodes of T in a cycle C so that the resulting graph remains planar. Unless otherwise
stated, we always assume that a Halin graph or its subgraphs are given in the planar embedded form. The
non-leaf nodes belonging to T are referred to as tree or internal nodes and the nodes in C are referred to
as cycle or outer nodes of H. A Halin graph with exactly one internal node is called a wheel. If H has at
least two internal nodes and w is an internal node of T which is adjacent to exactly one other internal node,
then w is adjacent to a set of consecutive nodes of C, which we denote by C(w). Note that |C(w)| ≥ 2.
The subgraph of H induced by {w} ∪ C(w) is referred to as a fan, and we call w the centre of the fan. See
Figure 4.

F

w

edge in C
edge in T
fan in H

Figure
1. A Halin graph with 3 fans. w is the centre of fan F .
Figure 4. A Halin graph H with 3 fans. w is the centre of fan F .
Lemma 2.1 (Cornuejols et al. [9]). Every Halin graph which is not a wheel has at least two fans.
Let G = (V, E) be a graph and let S ⊆ V be a connected subgraph of G. Let ϕ(S) be the cutset of S,
that is, the smallest set of edges whose removal disconnects S from the vertices in V \ S. Let G/S be the
graph obtained by contracting S into a single node, called a ‘pseudonode’ denoted by vS [9]. The edges in
G/S are obtained as follows:
3

(1) An edge with both ends in S is deleted;
AinHalin
with
3 fans. w is the centre
(2) An edge Figure
with both 1.
ends
G − Sgraph
remains
unchanged;
(3) An edge (v1 , v2 ) with v1 ∈ G − S, v2 ∈ S is replaced by the edge (v1 , vs ).

of fan F .

Lemma 2.2 (Cornuejols et al. [9]). If F is a fan in a Halin graph H, then H/F is a Halin graph.
Note that each time a fan F is contracted using the graph operation H/F , the number of non-leaf nodes
of the underlying tree is reduced by one. That is, after at most d(n − 1)/2e fan contractions, a Halin graph
will be reduced to a wheel.
Let w be the centre of a fan F , and label the outer nodes in F in the order they appear in C as,
u1 , u2 , . . . , ur (r ≥ 2). Let (j, k, l) be the 3-edge cutset ϕ(F ) which disconnect F from G such that j is
adjacent to u1 , k is adjacent to w but not adjacent to ui for any i, 1 ≤ i ≤ r, and l is adjacent to ur (See
Figure 5, r = 4).
Note that every Hamiltonian cycle τ in H contains exactly two edges of {j, k, l}. The pair of edges chosen
gives us a small number of possibilities for traversing F in a tour τ . For example, if τ uses k and l, it contains
the subsequence w, u1 , u2 , . . . , ur (call this a left-traversal of F ), if τ uses j and k it contains the subsequence
u1 , u2 , . . . ur , w (call this a right-traversal of F ) and if τ uses j and l, it contains a subsequence of the form
u1 , u2 , . . . , ui , w, ui+1 , . . . , ur , for some i ∈ {1, 2, . . . , r − 1} as it must detour through the centre of F (call
this a centre-traversal of F ).

j
F

u1
u2

u3
v

k

edge in C
edge in T
fan in H
u4

l

Figure
A Halin
H containing
fan
F a. 3-edge
{j, k,cutset
l} is which
a 3-edge
cutset
Figure
5. 2.
A Halin
graphgraph
H containing
fan F . {j, k,
l} is
disconnects
disconnects F from H.
Fwhich
from H.
1

3. Complexity of QTSP on Halin graphs
Many optimization problems that are NP-hard on a general graph are solvable in polynomial time on a
Halin graph [9, 24, 25]. In particular, TSP on a Halin graph is solvable in linear time. Unlike this special
case, we show that QTSP is strongly NP-hard on Halin graphs. The decision version of QTSP on a Halin
graph, denoted by RQTSP, can be stated as follows:
P
e∈τ c(e) +
P “Given a Halin graph H and a constant θ, does there exist a tour τ in H such that
q(e,
f
)
≤
θ?”
e,f ∈τ
Theorem 3.1 (Woods [31]). RQTSP is NP-complete even if the values c(e) ∈ {0, 1} and q(e, f ) ∈ {0, 1}
for e, f ∈ H.
Proof. RQTSP is clearly in NP. We now show that the 3-SAT problem can be reduced to RQTSP. The
3-SAT problem can be stated as follows: “Given a Boolean formula R in Conjunctive Normal Form (CNF)
containing a finite number of clauses C1 , C2 , . . . , Ch on variables x1 , x2 , . . . , xt such that each clause contains
4

exactly three literals (L1 , . . . , L3h where for each i, Li = xj or Li = ¬xj for some 1 ≤ j ≤ t), does there
exists a truth assignment such that R yields a value ‘true’ ?”
From a given instance of 3-SAT, we will construct an instance of RQTSP. The basic building block of our
construction is a 4-fan gadget obtained as follows. Embed a star on 5 nodes with center v and two specified
nodes ` and r on the plane and add a path P from ` to r covering each of the pendant nodes so that the
resulting graph is planar (see Figure 6). Call this special graph a 4-fan gadget.

µ1

µ2

µ3
r

`

v
Figure
4-fan
gadget
constructed
by embedding
starinon
nodes
the
Figure 6.3.4-fan
gadget
constructed
by embedding
a star on 5anodes
the4plane
andinadding
a path.and adding a path connecting the pendant nodes so that the resulting
plane
graph is planar.

The nodes on path P of this gadget are called outer nodes and edges on P are called outer edges. Let
µ1 , µ2 , µ3 be edges with distinct end points in P . Note
C1 that any `-r Hamiltonian path of the gadget must
contain all the outer edges except one which
is
skipped
to detour through v. We will refer to an `-r
µ
2
µ1
µ3
Hamiltonian path in a 4-fan gadget as a center-traversal
as
r1 before.
l1
We will construct a Halin graph H using one copy of the gadget for each clause and let µ1 , µ2 , µ3 correspond
to literals contained in that clause. We will assign costs to pairs of edges such that every Hamiltonian cycle
with cost 0 must contain a centre-traversal for each clause. To relate a Hamiltonian cycle to a truth
vy which does not contain edge µi corresponds
assignment, a centre-traversal
to an assignment of a true value
l2
µ4
to literal Li .
v1
y clause C1 , . . . , Ch , create a copy of µthe 4-fan gadget. The r, `, and v
Now construct H as follows. For each
5
nodes of the 4-fan gadget corresponding to the clause Ci are denoted by ri , `i andCv2i respectively. Connect the
6
node ri to the node `i+1 , i = 1, 2, . . . , h. Introduce nodes vxv2and vy and theµedges
(`1 , vx ), (vx , vy ), (vy , rh ).
vx w and connect it to vw
Also introduce a new node
x , vy and vi for i = 1, 2, . r.2. , h − 1. The resulting graph is
the required Halin graph H. See Figure
x 7.
Assign the cost c(e) = 0 for every edge in H. Let x = (vx , w) and y = (vy , w). Note that every tour
which contains edges x and y traverses every gadget using a centre-traversal. For each gadget: assign costs of
v4
v3
q(e, f ) = 1 for pairs of edges which are neither outer edges nor both adjacent to the same literal edge µ1 , µ2
or µ3 , and for all other pairs of edges within the gadget assign cost 0. For each variable xj , j = 1, . . . , n,
and all literals Lm , Lq (m 6=r4q) if xj = Lm = ¬Lq , assign cost q(µ0ml,3µ0q ) = 1 where µ0m and µ0q are edges
connecting µm (and µq ) to the
paired costs are assumed to be 0.
µ7
µ12respective 4-fan gadget centre v. All other
Suppose B is a valid truth assignment.
Then
in
each
clause
there
exists
at least one true literal. Consider
µ
8
µ11
C3gadget such that τ detours around
C4 the
a tour τ in H which contains
edges
r3 µ9 every
µ10 l4x and y and traverses
exactly one literal edge which corresponds to a literal which is true in B. Since the truth assignment is
valid, such a τ exists. Clearly τ has cost 0, since no costs are incurred by pairs of edges contained in a single
Figure 4. Example of the Halin graph constructed from F = C1 ∧ C2 ∧ C3 ∧ C4 .
gadget, nor are costs incurred of the form q(µ0a , µ0b ) where La = ¬Lb . The latter
must be true because in
any truth assignment, the variable corresponding to La , say xa , must be either assigned a value of true or
false. Suppose a cost of 1 is incurred by q(µ0a , µ0b ) and hence La = ¬Lb . If xa is true, and xa = La , then
Lb clearly must be false, so τ cannot detour to miss both µ0a and µ0b . The same contradiction arises, if xa is
false. Hence a yes instance of 3-SAT can be used to construct a yes instance for RQTSP with θ = 0.
Now suppose there is a tour which solves RQTSP with θ = 0. Suppose τ 0 is such a tour. Clearly it
must use edges x and y, and hence must traverse every gadget via a centre-traversal. Such a detour must
5

v
Figure 3. 4-fan gadget constructed by embedding a star on 4 nodes in the
plane and adding a path connecting the pendant nodes so that the resulting
graph is planar.

C1
µ1

µ2

µ3
r1

l1

vy

l2
v1

y

µ5
µ6

v2
vx

C2

r2

w

x
v4

v3

r4

l3

µ12

µ7

C4

µ4

µ8

µ11

r3 µ 9

µ10 l4

C3

Figure 4. Example of the Halin graph constructed from F = C1 ∧ C2 ∧ C3 ∧ C4 .
Figure 7. Example of the Halin graph constructed from F = C1 ∧ C2 ∧ C3 ∧ C4 .

skip a literal edge in every gadget, otherwise a cost of 1 is incurred. Suppose D = {L1 , . . . , Ls } is the set
of literals which are skipped. Li 6= ¬Lj for any i, j, otherwise a cost of 1 is incurred. This implies that a
truth assignment which results in every literal in D being true is a valid truth assignment to the variables
x1 , . . . , xt . That is, for each literal edge which is skipped in τ 0 , assign true or false to the corresponding
variable such that the literal evaluates to true (if Li = xj , set xj = true and if Li = ¬xj , set xj = f alse).
The truth values for any remaining variables can be assigned arbitrarily. This truth assignment returns true
for each clause since exactly one literal in each clause is detoured, and evaluates to true. Hence this truth
assignment is a valid assignment for 3-SAT.


4. Complexity of k-neighbour TSP on Halin graphs
Let G be a planar embedding of a planar graph and e and f are two distinct edges of G. Then e and f
2 contains both e and f . This may include the outer
are said to be cofacial if there exists a face of G which
face.
Theorem 4.1. Let τ be a tour in the planar embedding H = T ∪ C of a Halin graph. Then, any two edges
adjacent in τ must be cofacial.
Proof. Suppose the result is not true. Then, there exists a tour τ in H containing two adjacent edges
e = (u, x), f = (x, v) such that e and f are not cofacial. From our previous discussion on fan traversals, we
can assume that x 6∈ C. Since e and f are not cofacial at x, there exists edges g = (y, x) and h = (x, z) in
H such that the clockwise ordering of edges incident on x is of the form f, . . . , g, . . . , e, . . . , h (See Figure 8).
Without loss of generality, assume T is rooted at x. Then T has at least four subtrees Tu , Tv , Ty , Tz rooted
respectively at u, v, y and z. Since τ is a tour containing the edge e, it must contain a path, say P1 , through
the subtree Tu from u to uc ∈ C. Note that uc could be the same as u and in this case the subtree Tu is
the isolated node u. Similarly, τ must contain a path P2 in Tv from v to vc ∈ C (See Figure 8). Note that
P = P1 ∪ P2 ∪ {e, f } is a path in τ . Deleting the vertex set V (P ) of P and its incident edges from H yields
a disconnected graph. Thus, τ − V (P ) must be disconnected, a contradiction.


A preliminary version of this result is given in [31].
6

yc

y

g
uc

P1

u

e

x

v

f

vc

P2

h
z

zc

Figure8.5.A A
Halin
graph
H non-consecutive
with non-consecutive
edges
andx.f Hat− node
x.
Figure
Halin
graph
H with
edges e and
f at enode
P where
P
P2 ∪ {e,Pf }=has
hence
no components,
τ contains bothhence
edges enoand
f.
H =−PP1 ∪where
P1 two
∪ Pcomponents,
two
τ contains
2 ∪ {e, f } has
both edges e and f .

x
A path in the planar embedding H = T ∪ C of a Halin
graph is called a candidate paths if its consecutive
α
α
5
edges are cofacial. A candidate path with k-edges is called 6a candidate k-path. Note that only candidate
paths can be subpaths of a tour but it is possible that kthere are candidate paths that are not part of a tour.

Corollary 4.2. Let H = T ∪ C be a planar embedding of a Halin graph
a specified edge of H.
α4 and eαbe
α2
3
w
Then, H has at most k α
· 21k−1 candidate
k-paths containing
e.
Proof. Consider extending e, if necessary in either directions in H, to a candidate k-path P . For a given
u
u0
end point of a sub path of P , say
vertex u, tby
are onlyr+1
two possible edges incident on
1 Theorem 4.1,tthere
r
u, which may belong to P . Thus, there are at most 2k−1 candidate k-paths when the position of e is fixed.
Since e can take any of the k positions
in a candidate k-path, there arel at most k · 2k−1 candidate k-paths
j
u1
ur
containing e.



yr−1

y1

As an immediate consequence of Corollary 4.2, we have an upper bound of 2n−2 on the number of
Hamiltonian cycles in a Halin graph. To see this, let r be the number of Hamiltonian cycles in H. From
Figure 6. A fan F with centre w. Every τ containing j and k contains
each such cycle, we can generate n distinct Hamiltonian paths (candidate (n − 1)-paths) by ejecting an edge.
edges
. . ,Hamiltonian
yr−1 , tr . Every
l contains
y1and
, . . . all
, yr−1
, t1paths
.
1 , .all
Repeating
this yfor
cyclesτ incontaining
H, we get k
rnand
candidate
(n − edges
1)-paths
these
are
Every
τ
containing
j
and
l
must
contain
one
of
the
subpaths
from
the
set
distinct. Hence rn is a lower bound on the number of candidate (n − 1)-paths in H. By Corollary 4.2,
(n − 1)2n−2
upper
Thus,
{α1is−anj −
l − bound
α3 , α1on
− the
j −number
l − α4 ,ofαcandidate
− −α1)-paths
l−
α4 }.rn ≤ (n − 1)2n−2 and
2 − j − l (n
3 , α2 − jin−H.
n−1 n−2
n−2
hence r ≤ n 2
≤2
.
Noting that there are at most 2(n − 1) edges in H and that the number of quadratic costs which are
relevant is the number of candidate k-paths, it follows from Corollary 4.2, that the number of quadratic
costs which are relevant is bounded above by k · 2k · (n − 1) = O(n) for any fixed k and O(nt+2 ) if k ≤ t log n.
Note that any face of H must contain an outer edge. Moreover, the following Corollary will prove useful.
Corollary 4.3. If H is embedded in the plane such that it is planar and C defines the outer face, for any
outer edge e which is contained in the outer face and face Fe , every tour which does not contain e must
contain all other edges of Fe .
7

3

4.1. TSP(3) on Halin graphs. As indicated earlier, TSP(1) is the same as TSP, which is solvable in linear
time on Halin graphs [9]. TSP(2) can also be solved in linear time by appropriate modifications of the
algorithm of [25] as indicated in [33]. However, for k ≥ 3, such modifications do not seem a viable option.
We now develop a linear time algorithm to solve TSP(3).
Let us start with an alternative formulation of TSP(3). For any subgraph G of H, let P3 (G) be the
collection of all distinct candidate 3-paths in G. For each candidate 3-path (e, f, g) ∈ P3 (H), define
q(e, f, g) = q(e, g) +

q(e, f ) + q(f, g) c(e) + c(f ) + c(g)
+
.
2
3

(4.1)

Now consider the simplified problem:
ST SP (3) :

Minimize

X

q(e, f, g)

(e,f,g)∈P3 (τ )

Subject to

τ ∈ F.

Theorem 4.4. Any optimal solution to the STSP(3) is also optimal solution to TSP(3).
Proof. For any τ ∈ F,
X
q(e, f, g)
(e,f,g)∈P3 (τ )



q(e, f ) + q(f, g) c(e) + c(f ) + c(g)
+
=
q(e, g) +
2
3
(e,f,g)∈P3 (τ )
X
X
=
q(e, f ) +
c(e).
X

(e,f )∈δ(3,τ )



e∈δ(τ )

Thus, the objective function values of STSP(3) and TSP(3) are identical for identical solutions. Since the
family of feasible solutions of both these problems are the same, the result follows.


In view of Theorem 4.4, we restrict our attention to STSP(3).
For TSP(1), Cornuejols et al. [9] identified costs of new edges generated by a fan contraction operation
by solving a linear system of equations. This approach cannot be extended for any k-neighbour TSP for
k ≥ 3 as it leads to an over-determined system of equations which may be infeasible. Instead, we extend the
penalty approach used in Phillips et al. [25]. The idea here is to introduce a node-weighted version of the
problem STSP(3) where we use a penalty function for the nodes of C, the value of which depends on the
edges chosen to enter and exit the node, along with some other ‘candidate’ edges. We iteratively contract
the fans in H, storing the appropriate values of suitable subpaths as we traverse the fans in a recursive
way. Once we reach a wheel, we can compute an optimal tour for the resulting problem. Backtracking by
recovering appropriate subpaths from contracted fans in sequence, an optimal solution can be identified.
To formalize the general idea discussed above, let us first discuss the case where H is a Halin graph which
is not a wheel. In this case, H will have at least two fans.
Let F be an arbitrary fan in H with w as the centre. Label the outer nodes of F in the order they
appear in C, say, u1 , u2 , . . . , ur (r ≥ 2). Let {j, k, l} be the 3-edge cutset ϕ(F ) which disconnects F from H
such that j is adjacent to u1 , k is adjacent to w and l is adjacent to ur . Let j = (u1 , u0 ), k = (w, x) and
l = (ur , ur+1 ). There are exactly two edges not connected to F which are cofacial with k and incident on
x. The first edge which follows k in the clockwise orientation of edges incident on x is denoted α5 , and the
other edge incident on x and cofacial with k is denoted by α6 . (See Figure 9.) There are exactly two edges
not connected to F and incident on u0 . These edges are labelled α1 , α2 . Likewise, there are exactly two
edges not connected to F and incident on ur+1 . These edges are labelled α3 , α4 . (See Figure 9.) Without
loss of generality α1 , α3 are in C and α2 , α4 are in T . It is possible that α2 could be the same as α5 and also
possible that α4 could be the same as α6 .
To complete a fan contraction operation, we consider the 3 types of traversals of F . We define a penalty
function stored at nodes (pseudonodes) of C which contains attributes of a minimum traversal of F of each
type. For any left- or right-traversal of F , there is a single path through F using all cycle edges. Any tour
which includes j and k must pass through one edge of the pair incident on u0 lying outside F together with
edges y1 , . . . , yr−1 , tr , k, α6 . Similarly, any tour which includes k and l must pass through one edge of the
pair incident on ur+1 lying outside F together with edges yr−1 , . . . , y1 , t1 , k, α5 . Any tour which includes j
and l must also pass through one edge in each of the pairs of edges incident on u0 (or ur+1 ) lying outside
8

z

zc

F . That is, every tour τ containing j and l must contain a path containing one collection of edges from the
set {(α1 ,Figure
j, l, α3 ), (α5.
l, α
, j, l, α3 ),
α4 )}. We refer to aedges
centre-traversal
of Fnode
whichx.bypasses
1 , j,A
4 ), (α2graph
2 , j, l, non-consecutive
Halin
H(αwith
e and f at
y1 ∈ F ∩ C as a left path, one which bypasses ys ∈ F ∩ C for some s ∈ [2, r − 2] as a middle path, and one
H − P where P = P ∪ P ∪ {e, f } has two components, hence no τ contains
which bypasses yr−1 ∈ F ∩ C as 1a right2 path.

both edges e and f .

α5

x

α6
k

α2

α1

α4

w

u0

t1

ur+1

tr

j
u1

α3

ur

l

yr−1

y1

Figure9. 6.
A Ffan
F centre
withw.centre
Every jτand
containing
j and
Figure
A fan
with
Every τw.
containing
k contains edges
y1 ,k. . .contains
, yr−1 , tr .
Every
τ
containing
k
and
l
contains
edges
y
,
.
.
.
,
y
,
t
.
Every
τ
containing
j
and
l must
edges y1 , . . . , yr−1 , tr . Every τ containing
k and
, t1 .
1
r−1 l 1contains edges y1 , . . . , yr−1
contain
one
of
the
subpaths
from
the
set
{α
−
j
−
l
−
α
,
α
−
j
−
l
−
α
,
α
−
j
−
l
−
α
1
4
2 from the
3 , αset
2−
Every τ containing j and l must contain
one3 of1 the subpaths
j − l − α4 }.
{α1 − j − l − α3 , α1 − j − l − α4 , α2 − j − l − α3 , α2 − j − l − α4 }.

Let S be the set of nodes (pseudonodes) in C at some iteration in the contraction process. In TSP(3),
quadratic costs are ‘absorbed’ during each fan contraction operation, depending both on the edges in F and
within a distance 2 from F , so care must be taken to retain the proper information. That is, in order to
develop an extension of the penalty approach used in Phillips et al. [25] for TSP(3), we extend the penalty
function stored at the nodes (pseudonodes) in C that depends on an additional parameter ρ, which specifies
the structure of edges around each pseudonode. Note that due to the recursive property of pseudonodes where
a fan contraction operation may ‘absorb’ pseudonodes, the parameter ρ specifies a shape of the structure
rather than explicitly stating the edges surrounding a pseudonode. Further, we define a function β which
stores the penalty values associated with ρ.
3 0), L = (1, 0), R = (0, 1), B = (1, 1)} and A2 be the
Let A1 be the collection of ordered pairs {M = (0,
collection of ordered pairs {(1, 3), (1, 4), (1, 6), (2, 3), (2, 4), (2, 6), (5, 3), (5, 4)}. At each node i ∈ S we define
12
1
2
21 22
2
ρi = (ρ1i , ρ2i ) where ρ1i = (ρ11
i , ρi ) ∈ A and ρi = (ρi , ρi ) ∈ A . ρi indicates which penalty value (to be
defined shortly) stored at pseudonode i is to contribute to the objective function value. The first component
of ρi is a binary vector of length 2 which specifies the inner structure of i (edges y1 , t1 , yr−1 and tr prior
to any fan contractions such that the first component is 0 if y1 is selected, and 1 if t1 is instead, and the
second component is 0 if yr−1 is selected, and 1 if tr is instead), and the second component of ρi , the outer
structure (α1 to α6 prior to any contraction of adjacent pseudonodes). Let ρ be the vector containing ρi for
every i ∈ S. Let ρH/F be the restriction of ρ to the vertices in H/F and augmented by ρvF ∈ {(a, b)}. Let
βi (ρi ) be the penalty that is incurred if ρi occurs at i.
For i ∈ C define:
(
βi (ρi ) if ρi is defined,
Pi (τ, ρi ) =
0
otherwise.
Since the penalties stored at i ∈ S depend on edges which are not incident with i, and the dependent
edges may be ‘absorbed’ into adjacent pseudonodes so that not every ρ is feasible for a given τ . That is, the
inner and outer structures of adjacent pseudonodes in C must agree. Formally, we say that ρ is feasible for
τ if the following conditions are satisfied for every pseudonode i
(1) j, k ∈ τ ⇐⇒ ρ22
i = 6 and
(2) k, l ∈ τ ⇐⇒ ρ21
i = 5,
9

Figure 7. A tour τ in a wheel, which skips edge ci .

ci−1

ci+1

ti+1

ti
w

ui+1

i
and for every pair of consecutive upseudonodes
i, i + 1 ∈ C

(1)
(2)
(3)
(4)

ρ12
i
ρ12
i
ρ22
i
ρ22
i

=1
=0
=3
=4

⇐⇒
⇐⇒
⇐⇒
⇐⇒

ρ21
i+1
ρ21
i+1
ρ11
i+1
ρ11
i+1

= 2,
ci
= 1,
= 0 and
= 1.

ti+1

ti
ci

ui+1

ui

c

ci+1 For an example i−1
Let F 0 be the set of all feasible (τ, ρ) pairs.
of a feasible (τ, ρ) pair, see Figure 10.
Figure 8. Wheel H with center w considered as a fan.

F1

F2

F3

Figure
of Hofwhich
becomes
a fan after
contracting
F1 , F2 and F3F. ,The
Figure10.9. AAsubgraph
subgraph
H which
becomes
a fan
after contracting
1 F2
bold edges depict a centre-traversal of F contained in Hamiltonian cycle τ . Since τ contains
and F3 . The
bold edges depict a centre-traversal of F contained in Hamilton
the edges
t1 and yr−1 (relative to F1 ), the inner structure of vF1 must be (1, 0), and since
cycle
τ
.
A
(τ,
ρ F11 ),=the
((1,
0), (2,
3)), ρvofF2 v=
((0, 1), (1, 3))
τ contains edges ρ)
α2 pair
and αcontaining
outer
structure
3 (relative to vF
F1 must be (2, 3).
and ρis,vF3a =
((0, 0),
6)) is
feasible.
which
correspond
That
feasible
(τ, (2,
ρ) pair
must
contain The
ρvF1 edges
= ((1, 0),
(2, 3)).
Consideringtoallthe
of Finner
1 , F2
and
F
,
every
feasible
(τ,
ρ)
pair
contains
ρ
=
((1,
0),
(2,
3)),
ρ
=
((0,
1),
(1,
3))
and
3
vF2 correspond to the
structure
of ρvF2 are coloured in blue vand
the edges which
F1
ρ
=
((0,
0),
(2,
6)).
The
edges
which
correspond
to
the
inner
structure
of
ρ
are
coloured
vF3
vF2
outer
structure of ρvF2 are coloured in red.
in blue and the edges which
correspond to the outer structure of ρvF2 are coloured in red.

The problem now contains a cost for every triplet of consecutive edges in tour τ and additionally, a penalty
4
at each outer node i. Consider the modified 3-Neighbour
TSP on a Halin graph defined as follows:
M T SP (3) :

Minimize

X

z(τ, ρ) =

(e,f,g)∈P3 (τ )

Subject to

q(e, f, g) +

X
i∈C

Pi (τ, ρi )

(τ, ρ) ∈ F 0 .

The necessary costs to construct MTSP(3) can be obtained as required by applying (4.1) or by first
embedding H in the plane, and evaluating the candidate k-paths from Corollary 4.2. Note that Pv (τ, ρv )
can be computed in O(1) time by storing penalty 24-tuples containing the βv -values described in Table 1, at
each cycle node v. Also note that there may be O(2n ) feasible ρ vectors for a given τ , however, we show that
the optimal (τ, ρ) pair can be found in O(n)-time. It is also important to note that the set of pseudonodes
is retained for reasons which will become apparent.
In the initial graph, and for all ρi , i ∈ C, set βi (ρi ) = 0. For fan F in H, the penalties must be updated
to store the costs of traversing F when F is contracted to pseudonode vF . Let K represent
P the traversal of
F which contains only edges in C. That is, K = j − y1 − · · · − yr−1 − l. Then q(K) = e−f −g∈K q(e, f, g)
represents the cost incurred by selecting the edges in K. Let τ (F ) and ρ(F ) be the restrictions of τ and ρ
to F , respectively.
Assign the minimum cost of the right-traversal (which contains αs , s ∈ {1, 2} and α6 ), with inner structure
of the first pseudonode a ∈ {L = (1, 0), M = (0, 0)} to βvF (a, (s, 6)). That is, assign to βvF (a, (s, 6)) the
sum of the costs along the traversal, q(αs − j − y1 − · · · − yr−1 − tr − k − α6 ), together with the minimum
feasible set of penalties on the outer nodes contained in F , u1 , u2 . . . , ur . Note that for the case that u1 6∈ S,
10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Penalty
Description
βvF ((0, ∗), (1, 6)) traversal of F with inner structure (0, ∗) and outer structure
βvF ((1, ∗), (1, 6)) traversal of F with inner structure (1, ∗) and outer structure
βvF ((0, ∗), (2, 6)) traversal of F with inner structure (0, ∗) and outer structure
βvF ((1, ∗), (2, 6)) traversal of F with inner structure (1, ∗) and outer structure
βvF ((∗, 0), (5, 3)) traversal of F with inner structure (0, ∗) and outer structure
βvF ((∗, 1), (5, 3)) traversal of F with inner structure (1, ∗) and outer structure
βvF ((∗, 0), (5, 4)) traversal of F with inner structure (0, ∗) and outer structure
βvF ((∗, 1), (5, 4)) traversal of F with inner structure (1, ∗) and outer structure
βvF ((0, 0), (1, 3)) traversal of F with inner structure (0, 0) and outer structure
βvF ((0, 1), (1, 3)) traversal of F with inner structure (0, 1) and outer structure
βvF ((1, 0), (1, 3)) traversal of F with inner structure (1, 0) and outer structure
βvF ((1, 1), (1, 3)) traversal of F with inner structure (1, 1) and outer structure
βvF ((0, 0), (1, 4)) traversal of F with inner structure (0, 0) and outer structure
βvF ((0, 1), (1, 4)) traversal of F with inner structure (0, 1) and outer structure
βvF ((1, 0), (1, 4)) traversal of F with inner structure (1, 0) and outer structure
βvF ((1, 1), (1, 4)) traversal of F with inner structure (1, 1) and outer structure
βvF ((0, 0), (2, 3)) traversal of F with inner structure (0, 0) and outer structure
βvF ((0, 1), (2, 3)) traversal of F with inner structure (0, 1) and outer structure
βvF ((1, 0), (2, 3)) traversal of F with inner structure (1, 0) and outer structure
βvF ((1, 1), (2, 3)) traversal of F with inner structure (1, 1) and outer structure
βvF ((0, 0), (2, 4)) traversal of F with inner structure (0, 0) and outer structure
βvF ((0, 1), (2, 4)) traversal of F with inner structure (0, 1) and outer structure
βvF ((1, 0), (2, 4)) traversal of F with inner structure (1, 0) and outer structure
βvF ((1, 1), (2, 4)) traversal of F with inner structure (1, 1) and outer structure
Table 1. Description of penalty 24-tuple stored at pseudonodes in C.

(1, 6)
(1, 6)
(2, 6)
(2, 6)
(5, 3)
(5, 3)
(5, 4)
(5, 4)
(1, 3)
(1, 3)
(1, 3)
(1, 3)
(1, 4)
(1, 4)
(1, 4)
(1, 4)
(2, 3)
(2, 3)
(2, 3)
(2, 3)
(2, 4)
(2, 4)
(2, 4)
(2, 4)

it is not possible to have an inner structure L or B, and βvF (L, (s, 6)) = βvF (B, (s, 6)) = ∞. Otherwise
( r
)
X
βvF (a, (s, 6)) = q(αs − j − y1 − · · · − yr−1 − tr − k − α6 ) +
min 0
βui (ρui )
(τ (F ),ρ(F ))∈F (F ):
ρ1u =a or B,ρ22
ur =6

i=1

1

= q(αs , j, y1 ) + q(K) − q(yr−2 , yr−1 , l) + q(yr−2 , yr−1 , tr ) + q(yr−1 , tr , k) + q(tr , k, α6 ) (4.2)
( r
)
X
+
min 0
βui (ρui ) .
(τ (F ),ρ(F ))∈F (F ):
ρ1u =a or B,ρ22
ur =6

i=1

1

We will explain how the minimum in (4.2) can be calculated efficiently later in this paper.
Similarly, assign the minimum cost of the left-traversal (which contains αt , t ∈ {3, 4}, and α5 ) with inner
structure a ∈ {M = (0, 0), R = (0, 1)} to βvF (a, (5, t)). In the case that ur 6∈ S, it is not possible to have an
inner structure R or B, and βvF (R, (5, t)) = βvF (B, (5, t)) = ∞. Otherwise
βvF (a, (5, t)) = q(α5 , k, t1 ) + q(k, t1 , y1 ) + q(t1 , y1 , y2 ) + q(K) − q(j, y1 , y2 ) + q(yr−1 , l, αt )
( r
)
X
+
min 0
βui (ρui ) .
(τ (F ),ρ(F ))∈F (F ):
ρ1ur =a or B,ρ21
u =5

(4.3)

i=1

1

Let K(yi ), i ∈ {1, . . . , r − 1}, be the centre-traversal of F which does not contain yi . Then q(K(yi ))
represents the cost incurred by the edges in K(yi ). That is,
q(K(y1 )) = q(K) + q(j, t1 , t2 ) + q(t1 , t2 , y2 ) + q(t2 , y2 , y3 ) − q(j, y1 , y2 ) − q(y1 , y2 , y3 ),
11

q(K(yp )) = q(K) + q(yp−2 , yp−1 , tp ) + q(yp−1 , tp , tp+1 ) + q(tp , tp+1 , yp+1 ) + q(tp+1 , yp+1 , yp+2 )
− q(yp−2 , yp−1 , yp ) − q(yp−1 , yp , yp+1 ) − q(yp , yp+1 , yp+2 ),
for p ∈ {2, . . . , r − 2}, and
q(K(yr−1 )) = q(K) + q(yr−3 , yr−2 , tr−1 ) + q(yr−2 , tr−1 , tr ) + q(tr−1 , tr , l)
− q(yr−3 , yr−2 , yr−1 ) − q(yr−2 , yr−1 , l).
Assign the minimum cost of the centre-traversal which contains αs , s ∈ {1, 2}, and αt , t ∈ {3, 4}, which has
inner structure a ∈ {L = (1, 0), M = (0, 0), R = (0, 1), B = (1, 1)} to βvF (a, (s, t)). In the case that u1 6∈ S
and a = L, there is a single path traversing F with inner structure L, namely, j − t1 − t2 − y2 − · · · − yr−1 − l,
so
( r
)
X
βvF (L, (s, t)) = q(αs , j, t1 ) + q(K(y1 )) + q(yr , l, αt ) +
min 0
βui (ρui ) ,
(4.4)
(τ (F ),ρ(F ))∈F (F ):
22
ρ12
ur =0,ρu2 =6

i=2

and when u1 ∈ S, we assign the cost of the minimum centre-traversal with inner structure L. Note that this
path detours some yg , g ∈ {2, . . . , r − 1}.









( r
)




X
q(αs , j, t1 ) + q(K(yg )) + q(yr , l, αt ) +
min 0
.
βui (ρui )
βvF (L, (s, t)) =
min

g∈{2,...,r−1} 
(τ (F ),ρ(F ))∈F (F ):


i=1


12


ρ11
u1 =1,ρr =0,




21
22
ρug =5,ρu

g+1

=6

(4.5)
Similarly, when a = R and ur 6∈ S, there is a single path traversing F with inner structure R, namely,
j − y1 − · · · − yr−2 − rr−1 − tr − l so
(r−1
)
X
βvF (R, (s, t)) = q(αs , j, y1 ) + q(K(y1 )) + q(tr , l, αt ) +
min 0
βui (ρui ) ,
(4.6)
(τ (F ),ρ(F ))∈F (F ):
22
ρ11
=6
u =0,ρu
1

i=1

r−1

and when ur 6∈ S, we assign the cost of the minimum centre-traversal with structure R. Note that this path
detours some yg , g ∈ {1, . . . , r − 2}.









( r
)




X
βvF (R, (s, t)) =
q(αs , j, y1 ) + q(K(yg )) + q(yr , l, αt ) +
min 0
βui (ρui )
.
min

g∈{1,...,r−2} 
(τ (F ),ρ(F ))∈F (F ):


i=1


11
12


ρu1 =0,ρr =1,




21
22
ρug =5,ρu

g+1

=6

(4.7)
Now consider a = M . If u1 ∈ S, ur ∈ S then βvF (M, (s, t)) is assigned the cost of the minimum path
detouring yg for g ∈ {1, . . . , r − 1}. If u1 (ur ) is not a pseudonode then the centre-traversal must contain y1
(yr−1 ) and 1 (r − 1) is removed from g from the following equation.









(r−1
)




X
βvF (M, (s, t)) =
min
q(αs , j, y1 ) + q(K(yg )) + q(yr , l, αt ) +
min 0
βui (ρui )
.

g∈{1,...,r−1} 
(τ (F ),ρ(F ))∈F (F ):


i=1


12


ρ11
u1 =0,ρur =0,




21
22
ρug =5,ρu

g+1

=6

(4.8)
12

Now consider a = B. This is the same as the case where a = M except for the inner structure.









(r−1
)




X
βvF (B, (s, t)) =
min
q(αs , j, y1 ) + q(K(yg )) + q(yr , l, αt ) +
min 0
βui (ρui )
.

g∈{1,...,r−1} 
(τ (F ),ρ(F ))∈F (F ):


i=1


11
12


ρu1 =1,ρur =1,




21
22
ρug =5,ρu

g+1

=6

(4.9)
All βvF which have not been assigned are not associated with a feasible ρvF and are assigned a value ∞.

Theorem 4.5. Suppose H = T ∪ C is a Halin graph which is not a wheel and F is a fan in H. If (τ ∗ , ρ∗ )
is an optimal tour pair in H then there exists a feasible ρ∗H/F in H/F such that (τ ∗ /F, ρ∗H/F ) is optimal in
H/F and z(τ ∗ , ρ∗ ) = z(τ ∗ /F, ρ∗H/F ).

Proof. Let S be the set of pseudonodes in H. Let vF be the pseudonode which results from the contraction
of F , and label the vertices and edges of F as in Figure 9. Given (τ ∗ , ρ∗ ), we construct (τ ∗ /F, ρ∗H/F ) as
follows. Let ρ∗H/F,i = ρ∗i ∀i 6∈ F and ρ∗H/F,vF corresponding to the structure of (τ ∗ , ρ∗ ) around F in H. That
is, τ contains an αi , αj path through F in H, so let
ρ∗H/F,vF = ((a, b), (c, d))
where
(
0
a=
1

if (u1 6∈ S and y1 ∈ τ ∗ ) or (u1 ∈ S and ρ∗11
u1 = 0)
∗
if (u1 ∈
6 S and y1 6∈ τ ) or (u1 ∈ S and ρ∗11
u1 = 1),

(

if (ur 6∈ S and yr−1 ∈ τ ∗ ) or (ur ∈ S and ρ∗12
u1 = 0)
∗
∗12
if (ur ∈
6 S and yr−1 6∈ τ ) or (ur ∈ S and ρu1 = 1),

b=

0
1



1
c= 2


5

if (u1 6∈ S and α1 ∈ τ ∗ ) or (u1 ∈ S and ρ∗21
u0 = 1)
∗
if (u1 ∈
6 S and α2 ∈ τ ) or (u1 ∈ S and ρ∗21
u0 = 2)
if (u1 ∈
6 S and α5 ∈ τ ∗ ) or (u1 ∈ S and ρ∗21
u0 = 5),



3
d= 4


6

if (ur 6∈ S and tr 6∈ τ ∗ ) or (ur ∈ S and ρ∗22
ur = 3)
∗
if (ur ∈
6 S and tr ∈ τ ) or (ur ∈ S and ρ∗22
ur = 4)
∗
∗22
if (ur ∈
6 S and tr ∈ τ ) or (ur ∈ S and ρur = 6).

and

Then (τ ∗ /F, ρ∗H/F,vF ) is feasible in H/F .
Using equations (4.2)-(4.9) and noting that all new triples which contain vF have q(e, f, g) = 0, we get
X
X
z(τ ∗ , ρ∗ ) =
q(e, f, g) +
Pi (τ ∗ , ρ∗i )
(e,f,g)∈P3 (τ ∗ )

=

X

=

X

X

q(e, f, g) +

(e,f,g)∈
P3 (τ ∗ −F )

=

i∈C

(e,f,g)∈
P3 (τ ∗ )\P3 (τ ∗ −F )

q(e, f, g) +

(e,f,g)∈
P3 (τ ∗ /F −vF )
z(τ ∗ /F, ρ∗H/F ).

X

X

q(e, f, g) +

i∈C\F

βi (ρ∗i ) +

X

βi (ρ∗i )

i∈F

βi (ρ∗i ) + βvF (ρvF )

i∈C\F

It remains to show that (τ ∗ /F, ρ∗H/F ) is optimal in H/F . Towards a contradiction, suppose there exists
a tour pair (τ 0 /F, ρ0H/F ) 6= (τ ∗ /F, ρ∗H/F ) such that z(τ 0 /F, ρ0H/F ) < z(τ ∗ /F, ρ∗H/F ). The calculations of the
minimums in equations (4.2)-(4.9) imply that τ 0 /F 6= τ ∗ /F . Using equations (4.2)-(4.9), we can expand F ,
extending (τ 0 /F, ρ0H/F ) to (τ 00 , ρ00 ) in H with z(τ 0 /F, ρ0H/F ) = z(τ 00 , ρ00 ). Then z(τ 00 , ρ00 ) = z(τ 0 /F, ρ0H/F ) <
13

z(τ ∗ /F, ρ∗H/F ) = z(τ ∗ , ρ∗ ), contradicting the optimality of (τ ∗ , ρ∗ ). Hence (τ ∗ /F, ρ∗H/F ) is optimal in H/F .


We now show that βvF can be updated in O(|F |)-time, by introducing a structure which allows to optimally
chain together the β-values for consecutive nodes in F ∩ C. Refer to the subgraph induced by the nodes
{w} ∪ {ua , ua+1 , . . . , ub } as pseudo-fan P Fa,b for (1 ≤ a ≤ b ≤ r). Define the minimum penalty associated
with pseudo-fan P Fa,b to be P Fa,b (c, d) for a, b ∈ {1, . . . , r} with inner structure c ∈ {0, 1}2 and outer
structure d = (d1 , d2 ) ∈ {(1, 3), (1, 4), (2, 3), (2, 4)}. Note that the inner structure of pseudo-fan P Fa,b refers
to the edges y1 , t1 and yr−1 , tr within fans Fa and Fb (which are contracted to pseudonodes ua and ub ),
respectively. The outer structure refers to the edges α1 , α2 and α3 , α4 with respect to fans Fa and Fb , if ua
and ub are considered as pseudonodes.
To compute P Fa,b (c, d) we use the following recursion which chains together the minimum β-values
through consecutive nodes in C while maintaining feasibility of ρ.
For c1 , c2 ∈ {0, 1}, d1 ∈ {1, 2} and d2 ∈ {3, 4}, and 1 ≤ i ≤ r − 1
P F1,1 ((c1 , c2 ), (d1 , d2 )) = βu1 ((c1 , c2 ), (d1 , d2 ))

(4.10)

P Fr,r ((c1 , c2 ), (d1 , d2 )) = βur ((c1 , c2 ), (d1 , d2 ))

(4.11)

P F1,i+1 ((c1 , c2 ), (d1 , d2 )) =

min

{P F1,i ((c1 , s), (d1 , t)) + βui+1 ((t − 3, c2 ), (s + 1, d2 ))}

(4.12)

min

{βui−1 ((c1 , t − 1), (d1 , s + 3)) + P Fi,r ((s, c2 ), (t, d2 ))}

(4.13)

s∈{0,1},t∈{3,4}

and
P Fi−1,r ((c1 , c2 ), (d1 , d2 )) =

s∈{0,1},t∈{1,2}

To prove that the recursions defined by (4.10)-(4.13) are correct, first consider the optimal
P F1,i+1 ((c1 , c2 ), (d1 , d2 )). The minimum feasible assignment of penalties for the nodes within pseudo-fan
P F1,i+1 is simply the minimum among optimal assignments of penalties for the nodes within pseudo-fan
P F1,i and the penalty at pseudonode ui+1 , such that these penalties are feasible. That is, the outer
structure of P F1,i must match the inner structure of ui+1 and vice-versa. By definition, this is precisely
min
P F1,i ((c1 , s), (d1 , t)) + βui+1 ((t − 3, c2 ), (s + 1, d2 )). An analogous argument holds for
s∈{0,1},t∈{3,4}

P Fi−1,r ((c1 , c2 ), (d1 , d2 )).
It is now possible to compute the minimum traversals of F used in equations (4.2)-(4.9). For example,
middle paths through F have a cost which minimizes the sum of the penalties on P F1,i−1 + βi and βi+1 +
P Fi+2,r , such that both pairs are feasible. Note that the minimum ρ(F ) has been found while performing
the recursion defined by equations (4.10)-(4.13). In the worst case, when all outer nodes in F belong to
S, we must compute P F1,1 , . . . , P F1,r−1 and P Fr,r , . . . , P F2,r , which can be done in O(|F |)-time. By precomputing these, one can evaluate the minimum traversals of F used in equations (4.2)-(4.9), in O(|F |)-time
and hence one can update βvF in O(|F |)-time.
We iteratively perform the fan contraction operation, updating costs and penalties until we are left with
a wheel. The optimal tour in H skirts the cycle C and detours exactly once through centre w, skipping
exactly one edge of C. Orient the cycle C in the clockwise direction. τ contains all edges in C except for the
skipped edge, say ci = (ui , ui+1 ), together with the two edges which detour around ci . Define function φ(ci )
for each edge ci = (ui , ui+1 ) ∈ E(C). Let ti and ti+1 be the tree edges adjacent to ui and ui+1 , respectively.
We will define
φ(ci )

=

q(ci−2 , ci−1 , ti ) + q(ci−1 , ti , ti+1 ) + q(ti , ti+1 , ci+1 )
+q(ti+1 , ci+1 , ci+2 ) − q(ci−2 , ci−1 , ci ) − q(ci−1 , ci , ci+1 )
−q(ci , ci+1 , ci+2 ).

Then, the optimal tour pair has





X
z(τ ∗ , ρ∗ ) = q(C) + min φ(ci ) + min
βuj (ρuj ) .
i:ci ∈C 

feasible ρ
uj ∈C

Suppose that we fix an edge ci in τ . Then H can be considered to be a fan as shown in Figure 12.
14

ci

ui

ci−1

ti

ci−2

ui

ci−1

ci+1

ti+1
ci
w

ti

ci−2

ui+1

ui+1

ci+2
ci+1

ti+1

ci+2

w

Figure
wheel,which
which
skips
Figure7.
11.AAtour
tour ττ in
in aa wheel,
skips
edgeedge
ci . ci .
ci−1

ci+1

ti+1

ti
w

Figure

ui
7.

ci−1

ui+1 edge c .
A tour τ in a wheel, which skips
i
ti+1
ti
ci
ci
ci+1
ti+1
ti u
u
i+1

ui

w

i

ci−1

ci+1

ui+1

t
Figure 8. Wheel i+1
H with center twi considered as a fan.
ci
ci
ui+1

ui

ci−1

ci+1

Figure 8. Wheel H with center w considered as a fan.

Figure 12. Wheel H with centre w considered as a fan. Note that edge ci is fixed and the
fan ‘wraps’ around the wheel, reusing edges ci−1 , ci , ci+1 , ti−1 , ti and ti+1 .

F1

F2

F3

Figure 9. A subgraph of H which becomes a fan after contracting F1 , F2
and F3 . The bold edges depict a centre-traversal of F contained in Hamilton
cycle τ . A (τ, ρ) pair containing ρvF1 = ((1, 0), (2, 3)), ρvF2 = ((0, 1), (1, 3))
and ρvF3 = ((0, 0), (2, 6)) is feasible. The edges which correspond to the inner
F1
F2
F3
structure of ρvF2 are coloured
in blue
and the edges
which correspond to the
outer structure
of ρvF2 are
red.
Figure
9. A subgraph
of coloured
H whichinbecomes
a fan after contracting F , F

Fix edge cr in τ and consider H to be a fan Fcr . Then the minimum tour in H can be determined
by
1
2
calculating
theFminimum
of theedges
minimum
centre-traversal
of Fcr and
which bypasses
cr (using, say,
and
depict
a centre-traversal
ofthe
F tour
contained
in Hamilton
3 . The bold
fan Fc1 ). cycle
This can
in O(r)-time
using
technique
above.
τ . be
A computed
(τ, ρ) pair
containing
ρvFthe
=pseudofan
((1, 0), (2,
3)), ρvdescribed
= ((0,
1), (1, 3))
F2
1
The preceeding discussion yields the following algorithm.

and ρvF3 = ((0, 0), (2, 6)) is feasible. The edges which correspond to the inner
15
4
structure of ρvF2 are coloured in blue and
the edges which correspond to the
outer structure of ρvF2 are coloured in red.

Algorithm 1 HalinTSP(3)(H, q, β)
Input: Halin graph H, quadratic cost function q, and penalty function β
if H is a wheel then
Use the wheel procedure to find an optimal tour τ in H
else
Let F be a fan in H
Contract F to a single node vF , using the Case 1 procedure. That is, assign penalties β to vF , assign
costs of 0 to all triples in H/F and assign costs of q to all remaining triples which are 3-neighbours in
H.
HalinTSP(3)(H/F , q, β)
end if
Expand all pseudonodes in reverse order and update τ
return τ
Each time that a fan is contracted, the number of tree nodes is reduced by 1, and hence the fan contraction
operation is performed one less than the number of non-leaf nodes in H. The fan contraction operation can
be performed in O(|F |)-time, and each time it is performed, the number of nodes in H is reduced by |F | − 1.
Since the wheel procedure takes O(n)-time, the total time for the algorithm is O(n).
4.2. TSP(k). We now show that the previous ideas can be extended to solve TSP(k). For any subgraph
G of H, let Pk (G) be the collection of all distinct candidate k-paths in G. For each candidate k-path
(e1 , e2 , . . . ek ) ∈ Pk (H), define
q(e1 , ek−1 ) + q(e2 , ek ) q(e1 , ek−2 ) + q(e2 , ek−1 ) + q(e3 , ek )
+
2
3
c(e1 ) + c(e2 ) + . . . + c(ek )
+ ... +
.
k
Now consider the simplified problem:
X
ST SP (k) : Minimize
q(e1 , e2 , . . . , ek )
q(e1 , e2 , . . . , ek ) =q(e1 , ek ) +

(4.14)

(e1 ,e2 ,...,ek )∈Pk (τ )

Subject to

τ ∈ F.

Theorem 4.6. Any optimal solution to the STSP(k) is also optimal for TSP(k).
Proof. Using equation (4.14), the proof of this follows along the same way as that of Theorem 4.4 and hence
is omitted.


As a result of Corollary 4.2, the preceding algorithm can be extended to solve TSP(k) by extending the
penalty functions at outer nodes to accommodate subpaths of length 2d(k+1)/2e .
A complete description of these varies as the information that needs to be stored is more involved and
is hence omitted. Some details however will be available in [32]. The complexity increases by a factor of
(2d(k+1)/2e ), which is constant for fixed k and polynomially bounded when k = t log n.
5. TSP(k) on fully reducible graph classes
We say that a class C of 3-connected graphs is fully reducible if it satisfies the following:
(1) If G ∈ C has a 3-edge cutset which partitions G into components S and S̄, then both G/S and G/S̄
are in C and we call G a reducible graph in C; and
(2) TSP can be solved in polynomial time for the graphs in C that do not have non-trivial 3-edge cutsets,
i.e. 3-edge cutsets that leave both components Hamiltonian. We call such graphs irreducible.
For instance, Halin graphs can be understood as graphs built up from irreducible fans connected to the
remainder of the graph via 3-edge cutsets. Cornuejols et al. [10] show that the ability to solve TSP in
polynomial time on irreducible graphs in C allows to solve TSP in polynomial time on all of C using facts
about the TSP polyhedron.
16

We remark that the algorithm of Section 4 can be used to show a somewhat similar statement for TSP(k).
Here we consider a graph class C that is fully k-reducible in the sense that either it can be subdivided
into irreducible graphs via 3-edge cutsets, or it is irreducible and it is possible to solve the k-neighbour
Hamiltonian path problem in polynomial time.
This requires solving the following problem:
X
X
M T SP (k) : Minimize
q(e1 , . . . , ek ) +
Pi (τ )
(e1 ,...,ek )∈Pk (τ )

Subject to

i∈V

τ ∈F

where Pi (τ ) is a penalty function for the pseudonode which depends on how tour τ traverses i, analogous to
the construction for the 3-neighbour TSP of section 4.
We recursively perform the contraction operation on the irreducible subgraphs of G, storing the necessary
tour information in the penalty at the resulting pseudonode. A similar result to Corollary 4.2 may be derived
to show that for any fixed k, this requires a polynomial number of penalties. The least cost traversals of S
can be computed in polynomial time using a generalization of the pseudo-fan strategy above.
Suppose the contraction operation is performed on a subgraph of size r in time O(P (r)), where P (r) is
a polynomial in r. Each time this operation is performed, the number of nodes in the graph is reduced by
r. This operation is performed at most n times and it follows that the entire algorithm can be performed in
polynomial time.
6. Conclusions
In this paper, we have shown that QTSP is NP-hard even when the costs are restricted to taking 0-1 values
on Halin graphs. We have presented a polynomial time algorithm to solve a restriction of QTSP, denoted
TSP(k) on any fully k-reducible graph for any fixed k. To illustrate this, we have given an algorithm which
solves TSP(3) on a Halin graph in O(n) time.
The k-neighbour bottleneck TSP on a Halin graph can be solved by solving O(log(n)) problems of the
type TSP(k). However, it is possible to solve the problem faster. Details will be reported elsewhere.
We would also like to thank Ante Ćustić for his useful comments.
References
[1] A. Aggarwal, D. Coppersmith, S. Khanna, R. Motwani, and B. Schieber. The angular-metric traveling salesman problem.
SIAM Journal on Computing, 29:697–711, 2000.
[2] D. Applegate, R. Bixby, V. Chvatal, and W. Cook. The traveling salesman problem: a computational study. Princeton
University Press, 2011.
[3] E. Arkin, Y. Chiang, J. Mitchell, S. Skiena, and T. Yang. On the maximum scatter traveling salesperson problem. SIAM
Journal on Computing, 29:515–544, 1999.
[4] E. Balas, R. Carr, M. Fischetti, and N. Simonetti. New facets of the STS polytope generated from known facets of the
ATS polytope. Discrete Optimization, 3:3–19, 2006.
[5] E. Balas, M. Fischetti, and W. Pulleyblank. The precedence-constrained asymmetric traveling salesman polytope. Mathematical Programming, 68:241–265, 1995.
[6] H. Bodlaender. Dynamic programming on graphs with bounded treewidth. In Automata, languages and programming
(Tampere, 1988),Lecture Notes in Comput. Sci., 317:105–118. Springer, Berlin, 1988.
[7] W. Chin and S. Ntafos. Optimum watchman routes. In Proceedings of the Second Annual Symposium on Computational
Geometry, 24–33. ACM, 1986.
[8] W. Cook. In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press,
2012.
[9] G. Cornuéjols, D. Naddef, and W. Pulleyblank. Halin graphs and the travelling salesman problem. Mathematical Programming, 26:287–294, 1983.
[10] G. Cornuéjols, D. Naddef, and W. Pulleyblank. The traveling salesman problem in graphs with 3-edge cutsets. Journal of
ACM, 32:383–410, April 1985.
[11] B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput., 85:12–
75, 1990.
[12] F. Della Croce, V. Paschos, and R. Calvo. Approximating the 2-peripatetic salesman problem. In Proc. Workshop on
Modelling and Algorithms for Planning and Scheduling Problems, MAPSP, 114–116, 2005.
[13] O. Ergun and J. Orlin. A dynamic programming methodology in very large scale neighborhood search applied to the
traveling salesman problem. Discrete Optimization, 3:78–85, 2006. The Traveling Salesman Problem.
17

[14] A. Fischer. An analysis of the asymmetric quadratic traveling salesman polytope. SIAM Journal on Discrete Mathematics,
28:240–276, 2014.
[15] A. Fischer and F. Fischer. An extended approach for lifting clique tree inequalities. Journal of Combinatorial Optimization,
30:489–519, 2015.
[16] A. Fischer, F. Fischer, G. Jäger, J. Keilwagen, P. Molitor, and I. Grosse. Exact algorithms and heuristics for the quadratic
traveling salesman problem with an application in bioinformatics. Discrete Applied Mathematics, 166:97–114, 2014.
[17] A. Fischer and C. Helmberg. The symmetric quadratic traveling salesman problem. Mathematical Programming, 142:205–
254, 2013.
[18] G. Gutin and A. Punnen, editors. The traveling salesman problem and its variations, volume 12 of Combinatorial Optimization. Springer New York, 2002.
[19] G. Jäger and P. Molitor. Algorithms and experimental study for the traveling salesman problem of second order. In B.
Yang, D. Du, and C. Wang, editors, Combinatorial Optimization and Applications, Lecture Notes in Computer Science,
5165:211–224. Springer Berlin, 2008.
[20] J. Krarup and I. Spadille. The peripatetic salesman and some related unsolved problems. Combinatorial programming:
methods and applications: proceedings of the NATO Advanced Study Institute held at the Palais des Congrès, Versailles,
France, 2-13 September 1974, 173, 1975.
[21] J. LaRusic and A. Punnen. The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical
analysis. Computers & Operations Research, 43:20–35, 2014.
[22] J. LaRusic, A. Punnen, and E. Aubanel. Experimental analysis of heuristics for the bottleneck traveling salesman problem.
Journal of heuristics, 18:473–503, 2012.
[23] E. Lawler, J. Lenstra, A. Kan, and D. Shmoys. The Traveling Salesman Problem: a guided tour of combinatorial optimization, volume 3. Wiley New York, 1985.
[24] D. Lou. An algorithm to find the optimal matching in Halin graphs. IAENG International Journal of Computer Science,
34:220–226, 2007.
[25] J. Phillips, A. Punnen, and S. Kabadi. A linear algorithm for the bottleneck traveling salesman problem on a Halin graph.
Information Processing Letters, 67:105–110, 1998.
[26] A. Oswin, A. Fischer, F. Fischer, F. Meier, U. Pferschy, A. Pilz, and R. Staněk Minimization and maximization versions
of the quadratic travelling salesman problem. Optimization, 66:521–546, 2017.
[27] G. Reinelt. The traveling salesman: computational solutions for TSP applications. Springer-Verlag, 1994.
[28] B. Rostami, F. Malucelli, P. Belotti and S. Gualandi. Quadratic TSP: A lower bounding procedure and a column generation
approach Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on, 377-384, September 2013.
[29] B. Rostami, F. Malucelli, P. Belotti, and S. Gualandi. Lower bounding procedure for the asymmetric quadratic traveling
salesman problem. European Journal of Operational Research, 253:584–592, 2016.
[30] R. Staněk, Problems on tours and trees in combinatorial optimization, PhD Thesis, Graz University of Technology, 2016.
[31] B. Woods. Generalized travelling salesman problems on Halin graphs. Master’s thesis, Simon Fraser University, Canada,
2010.
[32] B. Woods. The quadratic travelling salesman problem: complexity, approximations, and exponential neighbourhoods. PhD.
thesis In preparation, Simon Fraser University, Canada.
[33] B. Woods and A. Punnen. The quadratic travelling salesman problem on Halin graphs. Working paper, Simon Fraser
University, Canada, 2016.
(SFU) Department of Mathematics, Simon Fraser University, 250-13450 102 Avenue, Surrey, British Columbia,
V3T 0A3, Canada

18

