A class of exponential neighbourhoods for the quadratic travelling salesman problem

Abstract

The quadratic travelling salesman problem (QTSP) is to find a least-cost Hamiltonian cycle in an edge-weighted graph, where costs are defined on all pairs of edges such that each edge in the pair is contained in the Hamiltonian cycle. This is a more general version than the one that appears in the literature as the QTSP, denoted here as the adjacent quadratic TSP, which only considers costs for pairs of adjacent edges. Major directions of research work on the linear TSP include exact algorithms, heuristics, approximation algorithms, polynomially solvable special cases and exponential neighbourhoods (Gutin G, Punnen A (eds): The traveling salesman problem and its variations, vol 12. Combinatorial optimization. Springer, New York, 2002) among others. In this paper we explore the complexity of searching exponential neighbourhoods for QTSP, the fixed-rank QTSP, and the adjacent quadratic TSP. The fixed-rank QTSP is introduced as a restricted version of the QTSP where the cost matrix has fixed rank p. It is shown that fixed-rank QTSP is solvable in pseudopolynomial time and admits an FPTAS for each of the special cases studied, except for the case of matching edge ejection tours. The adjacent quadratic TSP is shown to be polynomially-solvable in many of the cases for which the linear TSP is polynomially-solvable. Interestingly, optimizing over the matching edge ejection tour neighbourhood is shown to be pseudopolynomial for the rank 1 case without a linear term in the objective function, but NP-hard for the adjacent quadratic TSP case. We also show that the quadratic shortest path problem on an acyclic digraph can be solved in pseudopolynomial time and by an FPTAS when the rank of the associated cost matrix is fixed.

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 hard combinatorial optimization problems. The TSP has been used to model a wide variety of applications. For details we refer the reader to the well-known books (Applegate et al. 2011; Cook 2012; Gutin and Punnen 2002; Lawler et al. 1985; Reinelt 1994). For clarity of discussion, we will refer to this problem as the linear TSP.

Let $G=(V,E)$ be an undirected graph on the vertex set $V=\{1,\ldots ,n\}$ and edge set $E=\{1,2,\ldots ,m\}$. For each edge $e \in E$, a cost c(e) is given. Also, for each pair of edges (e, f), another cost q(e, f) is prescribed. Let ${\mathcal {F}}$ be the set of all Hamiltonian cycles (tours) in G. The cost ${q}(\tau )$ of a tour $\tau \in {\mathcal {F}}$, where $\tau$ is represented by its edges, is given by

$$\begin{aligned} {q}(\tau ) = \sum \limits _{(e,f)\in \tau \times \tau } q(e,f) + \sum \limits _{e\in \tau } c(e). \end{aligned}$$

Then the quadratic travelling salesman problem (QTSP) is to find a least cost tour $\tau \in {\mathcal {F}}$ such that ${q}(\tau )$ is as small as possible.

The problem QTSP has received only very limited attention in the literature. A special case of QTSP has been studied by various authors recently (Fischer 2014, 2016; Fischer et al. 2014; Fischer and Helmberg 2013; Jäger and Molitor 2008; Rostami et al. 2016) where q(i, j) is assumed to be zero if edges i and j are not adjacent. Although this restricted problem is known as the quadratic TSP in the literature, to distinguish it from the general problem, we refer to it as the adjacent quadratic TSP, which we denote by QTSP(A). The k-neighbour TSP studied by Woods (2010) is also related to QTSP. The linear TSP on Halin graphs was studied in Cornuéjols et al. (1983), and an O(n) algorithm was given. In Woods and Punnen (2018b) it is shown that QTSP on Halin graphs is strongly NP-hard, however, an O(n) algorithm solves QTSP(A) on this class of graphs. The linear TSP is solvable in polynomial time when the set of tours is restricted to pyramidal tours (Burkard et al. 1999). In Woods and Punnen (2018a), it is shown that QTSP over the set of pyramidal tours in strongly NP-hard but the corresponding QTSP(A) can be solved in $O(n^3)$ over this class of tours.

Let Q be the m by m matrix with (e, f)th element q(e, f), for $e,f\in E$. If the rank of Q is p, then by using the rank decomposition of Q, QTSP can be written in another form as

$$\begin{aligned} \text {Minimize } q(\tau )&= \sum _{r=1}^p\left[ \left( \sum _{e\in \tau } a_e^r\right) \left( \sum _{e\in \tau }b_e^r\right) \right] + \sum _{e\in \tau }c(e) \\&\quad \text {Subject to } \tau \in {\mathcal {F}}. \end{aligned}$$

For the general QTSP, we can eliminate the linear term by adding c(e) to q(e, e). However, for the rank-restricted case, we need to consider the linear term explicitly since adding c(e) to q(e, e) could change the rank. The variation where the linear term is absent is called homogeneous rank p QTSP which is denoted by QTSP(p, H) and the general rank p QTSP is denoted by QTSP(p, c). It is easy to verify that QTSP(p, c) belongs to the class QTSP$(p+1,H)$. QTSP(p, c) and QTSP(p, H) restricted to pyramidal tours are studied in Woods and Punnen (2018a), to Halin graphs in Woods and Punnen (2018b), and is shown to be solvable in pseudopolynomial time when p is fixed, and additionally, admit an FPTAS when the costs are non-negative.

Since the TSP is a special case of QTSP(p, H), QTSP(p, c), QTSP(A) and QTSP, all these problems are strongly NP-hard (Garey and Johnson 1979).

Combinatorial optimization problems with the objective function as the product of two linear functions have been studied by Goyal et al. (2011) and Kern and Woeginger (2007). Mittal and Schulz (2013) considered a further general class of problems that subsumes the class of combinatorial optimization problems with objective functions as fixed sum of products of linear terms. Thus, QTSP(1, H) falls under the general class considered in Goyal et al. (2011), Kern and Woeginger (2007) and QTSP(p, c) falls under the class considered in Mittal and Schulz (2013). However, the corresponding results are not applicable to QTSP(p, c) because the conditions imposed in Mittal and Schulz (2013) to derive their results are not applicable to QTSP(p, c), even if $p=1$.

An instance of QTSP with cost matrix Q is said to be linearizable if there exists an instance of the linear TSP with cost matrix C such that for each tour, the QTSP and linear TSP objective function values are identical. The corresponding QTSP linearization problem is studied in Punnen et al. (2018) and necessary and sufficient conditions are obtained for a cost matrix Q to be linearizable.

Major directions of research work on the linear TSP include exact algorithms, heuristics, approximation algorithms, polynomially solvable special cases and exponential neighbourhoods (Gutin and Punnen 2002) among others. In this paper we explore the complexity of searching some specific exponential neighbourhoods for QTSP, QTSP(p, H) and QTSP(A). Our focus is on exponential neighbourhoods that are studied in literature for the linear TSP and are known to be polynomially searchable. The study offers additional insights into the structure of QTSP, QTSP(p, H), and QTSP(A) and enhance our understanding of the boundary between polynomially solvable cases and NP-hard instances of these models. In particular, we consider the following classes of exponential neighborhoods (which will be described in detail later):

• (1) Single edge ejection tours (SEE-tours) on a graph $G^*$ defined in Glover and Punnen (1997),

• (2) Double edge ejection tours (DEE-tours) on a graph $G^*$ defined in Glover and Punnen (1997),

• (3) Paired vertex graphs (PV-tours), and

• (4) Matching edge ejection tours (MEE-tours) (Bentley 1992; Deĭneko and Woeginger 2000; Gutin and Glover 2005; Glover and Rego 2018; Punnen 2001b).

Unlike the linear TSP, the QTSP is strongly NP-hard for all these classes of tours. Interestingly, the special cases of the QTSP(A) are polynomially solvable for three out of four of these classes while the QTSP(p, H) admits fully polynomial time approximation schemes (FPTAS). Our complexity results are summarized in Table 1.

Table 1 Summary of complexity results

In addition to their theoretical interest, exponential neighbourhoods are vital to the development of efficient very large-scale neighbourhood search (VLSN search) algorithms (Ahuja et al. 2002) and variable neighbourhood search algorithms (Mladenović and Hansen 1997) for a variety of hard combinatorial optimization problems. The success of a variable neighborhood search algorithm depends on the availability of simple neighborhoods that can be searched using very fast algorithms and more powerful neighborhoods, often of exponential size, that can be searched using ‘reasonable algorithms’, if not polynomial, to get the search process out of entrapments at local optima of simpler neighborhoods. In this sense, our study also contributes to the design of effective metaheuristics for QTSP(p, c) and QTSP(A). Some areas of applications of the QTSP model include modelling the permuted variable length Markov model in bioinformatics (Jäger and Molitor 2008) as well as an optimal routing problem for unmanned aerial vehicles (UAVs) (Woods et al. 2017). Orlin et al. (2004) showed that for any linear combinatorial optimization problem with every solution having non-negative cost, if a $\delta$-optimum over a neighborhood can be computed efficiently, then a $(\delta + \epsilon )$-local optimum for that neighborhood can be obtained efficiently. In Punnen (2018), this result is extended to a more general class of combinatorial optimization problems with some non-linear type objective functions. Exploiting these results, the FPTAS we obtained for QTSP(p, H) over various exponential neighborhoods can be utilized to construct fully-polynomial local optimization schemes (Orlin et al. 2004) for QTSP(p, H) with respect to the corresponding neighborhoods.

Throughout this paper, we use the following conventions. All matrices will be denoted by capital letters, and all vectors with bold characters. The ith component of a vector ${\mathbf {a}}$ is $a_i$. Paths are represented by tuples of vertices, i.e. $(v_1,v_2,v_3)$ is a path through vertices $v_1,v_2$ then $v_3$. Similarly, cycles are sometimes represented as ordered sets with the first and last elements the same, i.e. $(v_1,v_2,v_3,v_1)$ is the cycle which passes through $v_1$, $v_2$ and $v_3$ (in that order). When more convenient, cycles may be represented by its edges. For graph theoretic terminology and notations we refer to Bondy et al. (1976).

2 Single edge ejection tours on $G^*$

In this section we consider a special class of tours, called single edge ejection tours (SEE-tours), introduced by Glover and Punnen (1997). We now present various complexity results regarding QTSP and its variations, restricted to this class.

An SEE-tour is defined using a graph $G^*=(V,E)$ which is a spanning subgraph of $K_n$. Partition the vertex set of $K_n$ into a single vertex t, called the tip vertex and sets $V^1,V^2,\ldots ,V^m$, $m\ge 2$, such that $V^k =\{v^k_1,v^k_2,\ldots ,v^k_{r_k}\}$ and $|V^k|=r_k \ge 3$, for all $k=1,2,\ldots ,m$. Create a cycle $C(k)=(v^k_1,v^k_2,\ldots ,v^k_{r_k},v^k_1)$, for each $k=1,2,\ldots ,m$ and connect each vertex in $V^k$ to each vertex in $V^{k+1}$ by edges, for $k=1,2,\ldots ,m-1$. Let $E^k$ be the collection of edges obtained for $k = 1,2,\ldots ,m-1$. Add all possible edges from t to each vertex in $V^1$ and $V^m$. Let $E^0$ be the set of edges joining t and $V^1$, and $E^{m}$ be the set of edges joining t to $V^m$. The resulting graph is denoted by $G^*=(V,E)$ (see Fig. 1 for an example of a $G^*$ graph).

Fig. 1

A graph $G^*$ with $n=13$ and $m=3$

The travelling salesman problem on $G^*$ is known to be NP-hard (Glover and Punnen 1997) and it follows immediately that QTSP, QTSP(p, c), and QTSP(A) are all NP-hard on $G^*$. Let us now consider a family of tours in $G^*$, called single edge ejection tours (SEE-tours), which consists of all tours in $G^*$ which can be obtained by the following steps (Glover and Punnen 1997).

• (1) Choose an edge $(t,v^1_j)$ from t to the cycle C(1) and eject an edge $(v^1_j,v^1_{i})$ from C(1). The result creates a chain P(1) from t to $v^1_{i}$ which includes all edges of C(1) except for the ejected edge.

• (2) For each k from 2 to m, introduce the edge $(v^{k-1}_{i},v^k_j)$ from the vertex $v^{k-1}_{i}$ which is the end vertex of the chain $P(k-1)$ to the cycle C(k), and eject an edge $(v^k_j,v^k_{i})$ from C(k), where $i=j+1$ or $j-1$ modulo $r_k$, to create chain P(k) from t to $v^k_{i}$.

• (3) Add the edge $(v^m_{i},t)$ to close the chain P(m) to create a tour in $G^*$ (see Fig. 2 for an SEE-tour in the $G^*$ graph of Fig. 1).

Fig. 2

An SEE-tour in the graph $G^*$ given in Fig. 1

Let F(SEE) be the collection of SEE-tours in $G^*$. As indicated in Glover and Punnen (1997), $|F(SEE)|=2^m\prod _{k=1}^m|V^k|$. If $|V^k|=3$ for all k, then $|F(SEE)|=6^{(n-1)/3}\approx (1.817)^{n-1}$. If $|V^k|=4$ for all k, then $|F(SEE)|=8^{(n-1)/4}\approx (1.68)^{n-1}$. Thus finding a best TSP tour in F(SEE) is a non-trivial task. Glover and Punnen (1997) proposed an O(n) algorithm to solve the linear TSP when restricted to SEE-tours on $G^*$.

In the definition of QTSP, if the set of feasible solutions is restricted to the class of SEE-tours in $G^*$, we have an instance of QTSP-SEE. Although the linear TSP over SEE-tours can be solved in O(n) time, QTSP-SEE is a much more difficult problem.

Before discussing our complexity results, we present the definition of two well-known NP-hard problems that are used in our reductions; the quadratic unconstrained binary optimization problem (QUBO) and the partition problem (PARTITION).

QUBO:

Given a ${\gamma } \times {\gamma }$ cost matrix $Q=(q_{ij})_{{\gamma }\times {\gamma }}$, the problem QUBO is to find an ${\mathbf {x}}\in {\{0,1\}^\gamma }$ such that ${\mathbf {x}}^TQ{\mathbf {x}}$ is minimized.

PARTITION:

Given $\eta$ numbers $\alpha _1,\alpha _2,\ldots , {\alpha _\eta }$, the PARTITION problem is to determine if there exists subsets $S_1$ and $S_2$ of $\{1,2,\ldots ,{\eta }\}$ such that $S_1\cup S_2 =\{1,2,\ldots ,{\eta }\}$, $S_1\cap S_2 =\emptyset$, and $\sum _{j\in S_1}\alpha _j = \sum _{j\in S_2}\alpha _j$.

Theorem 2.1

QTSP-SEE is strongly NP-hard.

Proof

We reduce QUBO to QTSP-SEE. From an instance of QUBO, we construct an instance of QTSP-SEE as follows. For each variable $x_i$, $1\le i \le {\gamma }$, of QUBO, create a 3-cycle C(i). Choose an edge from each C(i) and label it i. Now construct the graph $G^*$ using these cycles. Arbitrarily label the remaining unlabeled edges of $G^*$ as ${\gamma }+1,{\gamma }+2,\ldots ,m$. Consider an $m\times m$ matrix $Q^{\prime }=(q^{\prime }_{ij})_{m\times m}$ where

$$\begin{aligned} q^{\prime }_{ij} = {\left\{ \begin{array}{ll} q_{ij}, &{} \text{ if } 1\le i,j \le {\gamma } \\ 0, &{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

Thus, $Q^{\prime }=\left[ \begin{array}{c|c} Q &{} {\mathcal {O}}\\ \hline {\mathcal {O}}^T &{} {\mathcal {O}}' \end{array}\right]$ where ${\mathcal {O}}$ and ${\mathcal {O}}'$ are the zero matrices of size ${\gamma } \times (m-{\gamma })$ and $(m-{\gamma })\times (m-{\gamma })$, respectively. Given any solution ${\mathbf {x}}=(x_1,x_2,\ldots ,{x_\gamma })$ of QUBO, we can construct an SEE-tour, $\tau$, in $G^*$ containing the edge i if $x_i =1$ and not containing i if $x_i=0$, for $1\le i \le {\gamma }$. Note that $\tau$ contains other edges as well. It can be verified that the cost of $\tau$ with cost matrix $Q^{\prime }$ is precisely ${\mathbf {x}}^TQ{\mathbf {x}}$ (Fig. 3).

Conversely, given any SEE-tour $\tau$ in the $G^*$ obtained above, construct a vector ${\mathbf {x}}= (x_1,x_2,\ldots ,{x_\gamma })$ by assigning $x_i=1$ if and only if edge i is in $\tau$, for $1\le i \le {\gamma }$. The cost of the tour $\tau$ with cost matrix $Q^{\prime }$ is precisely ${\mathbf {x}}^TQ{\mathbf {x}}$. Since QUBO is strongly NP-hard, the result follows. $\square$

Fig. 3

Construction of the graph $G^*$ used in the proof of Theorem 2.1

Let us now examine the complexity of some special cases of QTSP-SEE. In the definition of QTSP(p, c), if we restrict the solution set to SEE-tours in $G^*$, we have the instance QTSP(p, c)-SEE. That is, QTSP(p, c)-SEE is precisely the special case of QTSP-SEE where the rank of the associated cost matrix is p and a linear cost function is added to the quadratic costs. If the linear part is zero (i.e. homogeneous case), we denote the corresponding instance by QTSP(p, H)-SEE. Recall that there exist some vectors ${\mathbf {a}}^r$ and ${\mathbf {b}}^r$ for $r=1,\ldots ,p$ such that QTSP(p, c)-SEE can be stated as

$$\begin{aligned} \text {Minimize } q(\tau )&= \sum _{r=1}^p\left[ \left( \sum _{e\in \tau } a_e^r\right) \left( \sum _{e\in \tau }b_e^r\right) \right] + \sum _{e\in \tau }c(e) \\&\quad \text {Subject to } \tau \in F(SEE). \end{aligned}$$

Theorem 2.2

QTSP(p, c)-SEE is NP-hard even if $p=1$ and $c(e) =0$ for all $e \in E$.

Proof

We reduce the PARTITION problem to QTSP(1, H)-SEE. From an instance of PARTITION with data $\alpha _1,\ldots ,{\alpha _\eta }$, we construct an instance of QTSP(1, H)-SEE as follows.

For each $k=1,2,\ldots ,{\eta }$, create a 3-cycle C(k) on the vertex set $\{v_u^k,v_y^k,v_w^k\}$. Build the graph $G^*=(V,E)$ using these cycles. Define the weight for each edge $(i,j)\in E$ as follows: For $k=1,2,\ldots ,{\eta }$, assign weight $\alpha _k$ to edge $(v_y^k,v_u^k)$ and $-\alpha _k$ to the edge $(v_y^k,v_w^k)$. For $k=1,2,\ldots ,{\eta }-1$ assign weights $-M$ for $(v_u^k,v_y^{k+1})$ and $(v_w^k,v_y^{k+1})$ where $M= 1+{\sum _{k=1}^\eta |\alpha _k|}$. The weight of edge $(t,v_y^1)$ is ${\eta }M$, the weights of edges $(t,v^1_u)$ and $(t,v^1_w)$ are ${\eta }M + 1$, and the weights of edges $({v_u^\eta },t)$ and $({v_w^\eta },t)$ are $-M$, where t is the tip vertex of $G^*$. All other edges have weight zero (see Fig. 4 for a sample $G^*$ graph constructed.) Let $a_{ij}$ denote the weight of edge (i, j) constructed above and choose another set of weights $b_{ij}$ for edge (i, j), $i,j\in V$ such that $b_{ij}=a_{ij}$. Then, the objective function of QTSP(1, H)-SEE on the $G^*$ constructed above becomes $\left( \sum _{(i,j)\in \tau }a_{ij}\right) ^2$ where $\tau$ is an SEE-tour in this $G^*$. Note that zero is a lower bound on the optimal objective function value of QTSP(1, H)-SEE constructed above. It can be verified that the optimal objective function value of this QTSP(1, H)-SEE is zero precisely when the required partition exists. The result follows from the NP-completeness of PARTITION (Karp 1972). $\square$

Fig. 4

Construction of the graph $G^*$ used in the proof of Theorem 2.2. Note that the dotted edges do not belong to any optimal tour

Despite this negative result, we now show that when p is fixed, QTSP(p, H)-SEE can be solved in pseudopolynomial time and when the edge weights are non-negative it also admits an FPTAS. Recall that an instance of QTSP(p, H)-SEE is given by p pairs of costs $a^r_{ij}, b^r_{ij}$ for $r=1,2,\ldots ,p$, for each edge $(i,j)\in E$. We formulate QTSP(p, H)-SEE as a rank p quadratic shortest path problem (QSPP(p, H)) on a directed acyclic graph. It is well-known that QSPP(p, H) on an acyclic digraph is NP-hard even if $p=1$ (Punnen 2001a). The definition of this specific quadratic shortest path problem is given below.

Given the graph $G^*$, construct the acyclic digraph $G'=(V',E')$ with arc weight vectors ${\varvec{\alpha }}^r$, ${\varvec{\beta }}^r$, for $r=1,\ldots ,p$, as follows. Note that the vertex set $V^k$ of cycle C(k) in $G^*$ is represented by $V^k =\{v^k_1,v^k_2,\ldots ,v^k_{r_k}\}$. Also, the edge set of C(k) is $E(k) = \{e^k_1,e^k_2,\ldots ,e^k_{r_k}\}$ where $e^k_i = (v^k_i,v^k_{i+1})$ and the indices are taken modulo $r_k$. For $k=1,2,\ldots ,m$, create ${\hat{V}}^k =\{{\hat{v}}^{k}_1, {\hat{v}}^{k}_2,\ldots ,{\hat{v}}^{k}_{r_k}\}$. ${\hat{V}}^k$ can be viewed as a copy of $V^k$. Introduce two new vertices s and t, and define $V^{\prime }= \{s,t\}\cup \cup _{k=1}^{m} (V^k\cup {\hat{V}}^k)$. For each edge $(v^k_i,v^k_{i+1})$ in C(k), introduce a directed arc $(v^k_i,{\hat{v}}^k_{i+1})$ and another directed arc $(v^k_{i+1},{\hat{v}}^k_i)$ in $E'$, where the indices are taken modulo $r_k$. The directed arc $(v^k_i,{\hat{v}}^k_{i+1})$ represents the event of ejecting edge $e^k_i$ from C(k) where a Hamiltonian cycle “enters” C(k) through $v^k_i$ and “leaves” C(k) through $v^k_{i+1}$. For each $i=1,2,\ldots ,r_k$ and each $h=1,2,\ldots ,p$, set $\alpha ^h_{v^k_i,{\hat{v}}^k_{i+1}} = C(a^h,k)-a^h_{e^k_i}$ and $\beta ^h_{v^k_i,{\hat{v}}^k_{i+1}} = C(b^h,k)-b^h_{e^k_i}$, where $C(a^h,k)= \sum _{e\in C(k)}a^h_{e}$ and $C(b^h,k)=\sum _{e\in C(k)}b^h_{e}$. Similarly, the directed arc $(v^k_{i+1},{\hat{v}}^k_i)$ corresponds to ejecting edge $e^k_i$ from C(k) and a Hamiltonian cycle enters C(k) from $v^k_{i+1}$, traverses $v^k_{i+1},\ldots ,v^k_i$, and leaves C(k) through $v^k_i$. For $h=1,2,\ldots ,p$, set $\alpha ^h_{v^k_{i+1},{\hat{v}}^k_i} =\alpha ^h_{v^k_i,{\hat{v}}^k_{i+1}}$ and $\beta ^h_{v^k_{i+1},{\hat{v}}^k_i} =\beta ^h_{v^k_i,{\hat{v}}^k_{i+1}}$. For each edge $(v^k_i, v^{k+1}_j)$ connecting vertices in $V^k$ and $V^{k+1}$ introduce a directed arc $({\hat{v}}^k_i,v^{k+1}_j)$ in $E'$. For $h=1,2\ldots ,p$, set $\alpha ^h_{{\hat{v}}^k_i,v^{k+1}_j}=a^h_{v^k_i, v^{k+1}_j}$ and $\beta ^h_{{\hat{v}}^k_i,v^{k+1}_j}=b^h_{v^k_i, v^{k+1}_j}$. The tip vertex s is connected to $v^1_i$, for $i=1,2,\ldots ,r_1$, and the weights for directed arcs $(s,v^1_i)$ in $E'$ are set as $\alpha ^h_{s,v^1_i}=a^h_{t,v^1_i}$ and $\beta ^h_{s,v^1_i}=b^h_{t,v^1_i}$. These correspond to entering C(1) via the edge $(t,v^1_i)$. Similarly, every vertex $v^m_i$ is connected to t, for $i=1,2,\ldots ,r_m$, with weights set to $\alpha ^h_{{\hat{v}}^m_i,t} = a^h_{i,t}$ and $\beta ^h_{{\hat{v}}^m_i,t} = b^h_{v^m_i,t}$, and corresponds to leaving C(k) via the edge $(v^m,t)$. The graph $G'$ constructed from the graph $G^*$ in Fig. 1 is shown in Fig. 5.

Fig. 5

$G'$ constructed from the graph $G^*$ given in Fig. 1

Consider the homogeneous rank p quadratic shortest path problem on $G'$,

$$\begin{aligned}&{QSPP(p,H,G')}: \text {Minimize } q(P) = \sum _{r=1}^p \left( \sum _{e\in P}a^r_e\right) \left( \sum _{e\in P}b^r_e\right) \\&\quad \text {Subject to } P \in {\mathcal {P}}_{s,t}, \end{aligned}$$

where ${\mathcal {P}}_{s,t}$ is the set of all $s-t$ paths in $G'$.

Theorem 2.3

From an optimal ($\epsilon$-optimal) solution of QSPP$(p,H,G')$, an optimal ($\epsilon$-optimal) solution to QTSP(p, H)-SEE can be recovered in linear time.

Proof

From the construction of $G'$, it can be verified that there is a one-to-one correspondence between SEE-tours in $G^*$ and $s-t$ paths in $G'$. Moreover, the objective function values of the corresponding solutions of QTSP(p, H)-SEE and QSPP$(p,H,G')$ are identical, and the result follows. $\square$

In view of Theorem 2.3, to solve QTSP(p, H)-SEE (either by an exact algorithm or by an approximation algorithm), it is enough to solve a quadratic shortest path problem with cost matrix of rank p on an acyclic digraph (QSPP(p, H)). In QSPP(p, H), we assume that the cost matrix is given in rank decomposition form as vectors ${\mathbf {a}}^r$ and ${\mathbf {b}}^r$ for $r=1,2,\ldots ,p$. For the computational complexity of the quadratic shortest path problem and its various special cases, we refer to Rostami et al. (2018) and Hu and Sotirov (2018).

2.1 The QSPP(p, H)

We now present a labelling algorithm to solve QSPP(p, H) in pseudopolynomial time on an acyclic multidigraph $G=(V,E)$. Construct a distance function $\varvec{\delta }:(E,r)\rightarrow {\mathbb {R}}^{2p}$, which stores the values for ${\mathbf {a}}^r$ and ${\mathbf {b}}^r$ for $r=1,2,\ldots ,p$. Our algorithm stores a collection of distance label vectors, denoted $\Omega _j$, on each $j\in V$. A label ${\mathbf {d}}$ on vertex j represents the existence of a unique path $P^d_j$ from s to j such that the sums of the costs of ${\mathbf {a}}^r$ and ${\mathbf {b}}^r$ of edges in $P^d_j$, for each $r=1,2,\ldots ,p$, are equal to the entries of ${\mathbf {d}}$. Then, to solve QSPP(p, H), it suffices to find the distance label at t which minimizes the sum of products of its stored values. We now give the details of our approach.

Note that only vertices of G that lie on some $s-t$ path in G are relevant to QSPP(p, H). Thus, we can remove all vertices of G that are not reachable from s and those from which t is not reachable. Such vertices can be identified in $O(|V|+|E|)$ time by two applications of breadth-first search. Thus, without loss of generality, we assume that each vertex of G lies on some $s-t$ path in G, no incoming arcs to s, no outgoing arcs from t, the vertex set $V=\{1,2,\ldots ,n\}$ and the vertex labels follow topological order, $s=1$ and $t=n$.

For each arc $(i,j)\in E$, let $\varvec{\delta }_{ij}\in {\mathbb {R}}^{2p}$ be defined as

$$\begin{aligned} \delta _{ij}(h) = {\left\{ \begin{array}{ll} a^h_{ij} &{} \text { if } h=1,2,\ldots ,p \\ b^{h-p}_{ij} &{} \text { if } h=p+1,p+2,\ldots , 2p. \end{array}\right. } \end{aligned}$$

Our pseudopolynomial algorithm to solve QSPP(p, H) maintains a collection $\Omega _j$ of distance label vectors for all $j\in V$. Each distance label vector ${\mathbf {d}}\in \Omega _j$ belongs to ${\mathbb {R}}^{2p}$ and represents a unique path $P^{{\mathbf {d}}}_j$ from 1 to j in G such that

$$\begin{aligned} d(h) = {\left\{ \begin{array}{ll} \sum _{e\in P^{{{\mathbf {d}}}}_j} a^{r}_e &{} \text { if } h=1,2,\ldots ,p\\ \sum _{e\in P^{{{\mathbf {d}}}}_j} b^{r-p}_e &{} \text { if } h=p+1,p+2,\ldots ,2p. \end{array}\right. } \end{aligned}$$

For each $j\in V$, let $I(j)=\{i:(i,j)\in E\}$. Then, given $\Omega _i$ for $i\in I(j)$, the set $\Omega _j$ can be constructed by choosing distinct elements of the multiset

$$\begin{aligned} \{{\mathbf {d}}+\varvec{\delta }_{ij}:{\mathbf {d}}\in \Omega _i,i\in I(j)\}. \end{aligned}$$

(1)

Starting with $\Omega _1$ consisting of the zero vector in ${\mathbb {R}}^{2p}$, the sets $\Omega _2,\ldots ,\Omega _n$ can be generated using the formula (1). Let ${\mathbf {d}}^*\in \Omega _n$ be such that

$$\begin{aligned} \sum _{i=1}^p d^*(i) d^*(p+i) = \min _{{\mathbf {d}}\in \Omega _n} \left\{ \sum _{i=1}^{p} d(i)d(p+i)\right\} . \end{aligned}$$

Then $\sum _{i=1}^p d^*(i)d^*(p+i)$ gives the optimal objective function value of QSPP(p, H) on G with $s=1$, $t=n$ and each vertex in G lies on some path from 1 to n in G. The validity of this follows from the recursion defined by (1). Note that each distance label vector ${\mathbf {d}}\in \Omega _j$ is such that ${\mathbf {d}}={\mathbf {u}}+\varvec{\delta }_{ij}$ for some $i\in I(j)$ and ${\mathbf {u}}\in \Omega _i$. For each distance label ${\mathbf {d}}\in \Omega _j$, we maintain $pred({\mathbf {d}})=i$ which stores the predecessor vertex of distance label ${\mathbf {d}}$, and $pointer({\mathbf {d}})$ which is a pointer to an appropriate distance label in $\Omega _i$. A formal description of the algorithm is given below.

Lemma 2.4

$|\Omega _n|\ge |\Omega _j|$ for $j=1,2,\ldots ,n$.

Proof

Let $P=(\pi (1),\pi (2),\ldots ,\pi (r))$ be any path from vertex 1 to n in G. Consider a vertex $\pi (i)$, $i\in \{1,2,\ldots ,r-1\}$. Since the elements of $\Omega _{\pi (i)}$ are distinct vectors, the vectors that belong to $\{{\mathbf {d}}+\varvec{\delta }_{\pi (i)\pi (i+1)}:{\mathbf {d}}\in \Omega _{\pi (i)}\}$ are distinct. Thus, $|\Omega _{\pi (i+1)}|\ge |\Omega _{\pi (i)}|$. Since each vertex in G belongs to some path joining vertex 1 to vertex n, the result follows. $\square$

Theorem 2.5

QSPP(p, H) can be solved on an acyclic multidigraph G in $O(mn^{2p+1}U)$ time, where $U=\prod _{h=1}^p \max _{e\in E} |a^h_e| \max _{e\in E} |b^h_e|$, for any fixed p.

Proof

A topological order of the vertices in multidigraph G can be obtained in $O(n+m)$ time. For each $h=1,2,\ldots ,p$, the number of possible distinct values of $a^h$ for a label at any vertex is bounded by $2(n-1)\cdot \max _e |a^h_e|$. Similarly, the number of distinct values for $b^h$ is bounded by $2(n-1)\cdot \max _e |b^h_e|$. That is, $|\Omega _j| \le n^{2p}U$ for any $j\in V$, where $U=\prod _{h=1}^p \max _e |a^h_e| \max _e |b^h_e|$. To generate each $\Omega _j$, we consider each $\Omega _i$ such that $i\in I(j)$, and $|{\bar{\Omega }}|\le mn^{2p}U$. The distinct elements of ${\bar{\Omega }}$ can be found in $O(mn^{2p}U)$ time, and hence, all $\Omega _j$ can be constructed in $O(mn^{2p+1}U)$ time. Selecting a minimum ${\mathbf {u}}\in \Omega (n)$ such that $\sum _{i=1}^p u(i) u(p+i) = \min _{d\in \Omega _n} \{\sum _{i=1}^{2p} d(i)d(p+i)\}$ can be done in $O(p|\Omega _n|)$ time, and the result follows. $\square$

From Theorem 2.5, it follows that QSPP(p, H) on an acyclic digraph can be solved in pseudopolynomial time when p is fixed. As a consequence, QTSP(p, H)-SEE can be solved in pseudopolynomial time for fixed p.

Corollary 2.6

QTSP(p, H)-SEE can be solved in $O(mn^{2p+1}U)$ time, where $U=\prod _{h=1}^p \max _{e\in E} |a^h_e| \max _e |b^h_e|$.

Let us now observe that the QSPP(p, H) can be solved as a sequence of equality type resource-constrained shortest path problems (ECSPP) (Turner 2012). The average performance of this approach is likely to be weaker than that of the labelling algorithm when restricted to acyclic digraphs; this approach does not require the graph to be acyclic. However, the complexity of the procedure depends on that of solving ECSPP. Let $\eta _1,\eta _2,\ldots ,\eta _p$ be a set of parameters. Introduce the constraints $\sum _{e\in P}b^r_e=\eta _r$ for $r=1,2,\ldots ,p$ and consider the cost vector $\bar{{\mathbf {a}}}$ where ${\bar{a}}_e=\sum _{r=1}^p\eta _ra^r_e$. Solve the resulting ECSPP and let $P(\eta )$ be the resulting optimal solution. Repeating this for all possible values of $\eta =(\eta _1,\eta _2,\ldots ,\eta _p)$ and choosing the best solution amongst the solutions of these ECSPPs provides an optimal solution to QSPP(p, H). A variation of this solution approach can be extended to construct an FPTAS for QSPP(p, H) with non-negative weights.

We now turn our attention to establishing that QSPP(p, H) admits an FPTAS, and hence QTSP(p, H)-SEE also admits an FPTAS.

Theorem 2.7

(Mittal and Schulz 2013) For fixed m and $X\subseteq \{0,1\}^n$, let $f_i:X \rightarrow \mathbb {R}_+$ for $i=1,2,\ldots ,m$. Let $h:\mathbb {R}^m_+\rightarrow \mathbb {R}_+$ be any function that satisfies:

• (1) $h({\mathbf {y}}) \le h({\mathbf {y}}')$ for all ${\mathbf {y}},{\mathbf {y}}'\in \mathbb {R}^m_+$ such that $y_i\le y'_i$ for all $i=1,2,\ldots ,m$; and

• (2) $h(\lambda {\mathbf {y}})\le \lambda ^d h({\mathbf {y}}')$ for all ${\mathbf {y}}{,{\mathbf {y}}'}\in \mathbb {R}^m_+$ and $\lambda > 1$ for some fixed $d>0$.

There is an FPTAS for solving the general optimization problem: Minimize $g({\mathbf {x}}) = h(f_1({\mathbf {x}}),f_2({\mathbf {x}}),\ldots ,f_m({\mathbf {x}}))$, ${\mathbf {x}}\in X$ if the following exact problem can be solved in pseudopolynomial time: Given $k\in \mathbb {Z}$, $(c_1,c_2,\ldots ,c_n)\in \mathbb {Z}^n_+$, does there exist ${\mathbf {x}}\in X$ such that $\sum _{i=1}^n c_ix_i=k$?

Consider the homogenous fixed-rank quadratic optimization problem (rank-QOP), with rank p:

$$\begin{aligned}&\text {Minimize } q({\mathbf {x}}) = \sum _{r=1}^p {{\mathbf {a}}}^T_r {\mathbf {x}}\cdot {{\mathbf {b}}}^T_r {\mathbf {x}} \\&\quad \text {Subject to } {\mathbf {x}} \in X, \end{aligned}$$

where ${{\mathbf {a}}}_r,{{\mathbf {b}}}_r\in \mathbb {Z}^n_+$ and $X\subseteq \{0,1\}^n$. By setting $g=q$, $m=2p$, $f_r({\mathbf {x}})={\mathbf {a}}^T_r{\mathbf {x}}$, $f_{p+r}({\mathbf {x}})={\mathbf {b}}^T_r{\mathbf {x}}$, for $r=1,2,\ldots ,p$ and $h({\mathbf {y}})=\sum \limits _{r=1}^p y_r\cdot y_{p+r}$, it is clear that the conditions of Theorem 2.7 are satisfied with $d=2$. We have the following corollary.

Corollary 2.8

There exists an FPTAS for solving (rank-QOP) if the following exact problem can be solved in pseudopolynomial time: Given $k\in \mathbb {Z}$, $(c_1,c_2,\ldots ,c_n)\in \mathbb {Z}^n_+$, does there exist ${\mathbf {x}}\in X$ such that $\sum _{i=1}^n c_ix_i=k$?

Note that the exact shortest path problem is NP-hard. We relax the problem to that of finding a shortest walk that minimizes the QSPP(p, H) objective function. An optimal solution to the relaxed problem will have the same value as the optimal solution to the original problem since removing all cycles from any $s-t$ walk gives an $s-t$ path. Assuming that the weights are nonnegative, the exact problem can be solved in O(nmk) time by dynamic programming (Mittal and Schulz 2013). We now have the following corollaries which result from this discussion and the construction given above.

Corollary 2.9

QSPP(p, H) and QTSP(p, H)-SEE both admit an FPTAS when ${\mathbf {a}},{\mathbf {b}}\ge {\mathbf {0}}$.

The instance of QTSP(A) when the family of tours is restricted to F(SEE) is denoted by QTSP(A)-SEE. Our reduction of QTSP(p, H)-SEE to QSPP(p, H) discussed above cannot be applied directly to solve QTSP(A)-SEE. The reduction, however, can be modified to take into consideration the cost arising from adjacent pairs of edges to get an equivalent instance of adjacent QSPP(p, H) on an acyclic graph. Since the adjacent QSPP on an acyclic graph can be solved in polynomial time (Rostami et al. 2015), QTSP(A)-SEE can be solved in polynomial time. We present below a simple $O(n^2)$ algorithm to solve QTSP(A)-SEE directly.

We note that the QTSP(A) objective function only depends on consecutive edges in a tour. Moreover, since SEE-tours visit the cycles in $G^*$ sequentially, a dynamic programming algorithm naturally emerges. Refer to any chain P(k) that may be produced in the construction of an SEE-tour in $G^*$ as an SEE-Hamiltonian path of length k. A minimum cost SEE-Hamiltonian path of length k from t to $v^k_i$ can be expressed as a minimum of the SEE-Hamiltonian paths of length $k-1$ plus the costs induced by connecting each path to $v^k_i$. We now give the details of the procedure.

Without loss of generality, assume that the input for QTSP(A)-SEE is given as the costs of paths of length two in $G^*$. That is, for any 2-path ${(u,v,w)}$ with v as the middle vertex, a cost q(u, v, w) is given. Note that $q(u,v,w)=q(w,v,u)$. Let $f\left( v^k_i,v^k_{i+1}\right)$ be the length of a smallest SEE-Hamiltonian path in $G^*$ from t to $v^k_i$ when edge $\left( v^k_i,v^k_{i+1}\right)$ is ejected (assuming it contains edge $(t,v^1_{i+1})$ or $(v^{k-1}_j, v^k_{i+1})$) and let

$$\begin{aligned} g\left( v^k_i\right) = \sum _{s=1}^{r_k}q\left( v^k_s,v^k_{s+1},v^k_{s+2}\right) -q\left( v^k_i,v^k_{i+1},v^k_{i+2}\right) -q\left( v^k_{i-1},v^k_i,v^k_{i+1}\right) . \end{aligned}$$

In the above expression and that follows, we assume that the indices $r_k+1 \equiv 1, r_k+2 \equiv 2,$ and $0 \equiv r_k$. Then for $k=2,3,\ldots m$,

$$\begin{aligned} f(v^k_i,v^k_{i+1})&= \min _{1\le j\le r_{k-1}}\left\{ f\left( v^{k-1}_j,v^{k-1}_{j-1}\right) \right. +q\left( v^{k-1}_{j+1},v^{k-1}_j,v^{k}_{i+1}\right) \\&\quad +q\left( v^{k-1}_j,v^{k}_{i+1},v^k_{i+2}\right) +g\left( v^k_i\right) ,\\&\quad f\left( v^{k-1}_j,v^{k-1}_{j+1}\right) +q\left( v^{k-1}_{j-1},v^{k-1}_j,v^{k}_{i+1}\right) \\&\quad +q\left( v^{k-1}_j,v^{k}_{i+1},v^k_{i+2}\right) +\left. g\left( v^k_i\right) \right\} , \end{aligned}$$

and

$$\begin{aligned} f(v^k_i,v^k_{i-1})&= \min _{1\le j\le r_{k-1}}\left\{ f\left( v^{k-1}_j,v^{k-1}_{j-1}\right) \right. +q\left( v^{k-1}_{j+1},v^{k-1}_j,v^{k}_{i-1}\right) \\&\quad +q\left( v^{k-1}_j,v^{k}_{i-1},v^k_{i-2}\right) +g\left( v^k_{i-1}\right) ,\\&\quad f\left( v^{k-1}_j,v^{k-1}_{j+1}\right) +q\left( v^{k-1}_{j-1},v^{k-1}_j,v^{k}_{i-1}\right) \\&\quad +q\left( v^{k-1}_j,v^{k}_{i-1},v^k_{i-2}\right) +\left. g\left( v^k_{i-1}\right) \right\} . \end{aligned}$$

The values of $f\left( v^1_i,v^1_{i+1}\right)$ and $f\left( v^1_i,v^1_{i-1}\right)$ for $1\le i\le r_1$ can be calculated directly to initiate the above recursion. Thus we can compute the value of the SEE-Hamiltonian path from t to $v^m_i$ for each $i=1,2,\ldots ,r_m$. Adding the arc $(v^m_i,t)$ for $i=1,2,\ldots ,r_m$ yields a corresponding SEE-tour and a best such tour gives an optimal solution to QTSP(A)-SEE. The foregoing discussions can be summarized in the theorem below.

Theorem 2.10

QTSP(A)-SEE can be solved in $O(n^2)$ time.

3 Double edge ejection tours on $G^*$

In this section we consider a special class of tours, called double edge ejection tours (DEE-tours), introduced by Glover and Punnen (1997). We present various complexity results regarding QTSP and its variations restricted to this class.

The family of double edge ejection (DEE) tours in $G^*$ consists of all tours which can be obtained by the following steps.

• (1) Begin by extending two edges $(t,v^1_i)$ and $(t,v^1_{i+1})$ from t to the cycle C(1) and ejecting an edge $(v^1_i,v^1_{i+1})$ from C(1). The result creates an expanded cycle D(1) which includes all vertices of C(1) and t.

• (2) For each k from 1 to $m-1$, in that order, select an edge $(v^k_j,v^k_{j+1})$ of C(k) where $i\ne j$, and any edge $(v^{k+1}_s,v^{k+1}_{s+1})$ of $C(k{+1})$. Eject these two edges and add either the two edges $(v^k_j,v^{k+1}_j)$ and $(v^{k}_{j+1},v^{k+1}_{s+1})$ or the two edges $(v^k_j,v^{k+1}_{s+1})$ and $(v^{k}_{j+1},v^{k+1}_{s})$, creating the expanded cycle $D(k+1)$ containing the vertices of D(k) and $C(k+1)$.

• (3) The cycle D(m) is a DEE-tour in $G^*$ (see Fig. 6 for a DEE-tour in the $G^*$ graph of Fig. 1).

Fig. 6

A DEE-tour in the graph $G^*$ given in Fig. 1

The variation of QTSP when the family of feasible solutions are restricted to DEE-tours in $G^*$ is denoted by QTSP-DEE. Let F(DEE) be the collection of all DEE-tours in $G^*$. As indicated in Glover and Punnen (1997), $|F(DEE)|=2^{m-1}\prod _{k=1}^m |V^k|\prod _{k=1}^{m-1}|V^{k-1}|$. If $|V^k|=3$ for all k, then $|F(DEE)|=2^{m-1}3^{2m-1}\approx (1.26)^{n-4}\cdot (1.44)^{2n-7} \approx (2.61)^{n-4}$. If $|V^k|=4$ for all k, then $|F(DEE)|=2^{m-1}4^{2m-1}\approx (1.19)^{n-5}\cdot 2^{n-3}$. Despite the fact that this is an exponential class of tours, when the feasible solutions are restricted to DEE-tours in $G^*$, the linear TSP can be solved in O(n) time (Glover and Punnen 1997). This simplicity however does not extend to QTSP-DEE.

Theorem 3.1

QTSP-DEE is strongly NP-hard.

Proof

We reduce QUBO to QTSP-DEE. Without loss of generality, from an instance of QUBO on $2{\gamma } + 1$ variables, we construct an instance of QTSP-DEE as follows. Create a 3-cycle C(i) for $i=1,\ldots ,{\gamma }$. Choose two edges from each C(i), $i=1,\ldots ,{\gamma }-1$ and a single edge from $C({\gamma })$ and label these $1,2,\ldots ,2{\gamma }+1$. Now construct the graph $G^*$ using these cycles. Arbitrarily label the remaining unlabelled edges of $G^*$ as $2{\gamma }+2,2{\gamma }+3,\ldots ,m$. Consider an $m\times m$ matrix $Q'=(q'_{ij})_{m\times m}$ where

$$\begin{aligned} q^{\prime }_{ij} = {\left\{ \begin{array}{ll} q_{ij}, &{} \text{ if } 1\le i,j \le 2{\gamma }+1 \\ 0, &{} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

Thus, $Q^{\prime }=\left[ \begin{array}{c|c} Q &{} {\mathcal {O}}\\ \hline {\mathcal {O}}^T &{} {\mathcal {O}}' \end{array}\right]$ where ${\mathcal {O}}$, and ${\mathcal {O}}'$ are the zero matrices of size $2{\gamma }+1 \times (m-2{\gamma }-1)$ and $(m-2{\gamma }-1)\times (m-2{\gamma }-1)$, respectively. Given any solution ${\mathbf {x}}=(x_1,x_2,\ldots ,x_{2{\gamma }+1})$ of QUBO, we can construct a DEE-tour, $\tau$, in $G^*$ containing the edge i if $x_i =1$ and not containing i if $x_i=0$, for $1\le i \le 2{\gamma }+1$. Note that $\tau$ contains other edges as well. It can be verified that the cost of $\tau$ with cost matrix $Q^{\prime }$ is precisely ${\mathbf {x}}^TQ{\mathbf {x}}$.

Conversely, given any DEE-tour $\tau$ in the $G^*$ obtained above, construct a vector ${\mathbf {x}}= (x_1,x_2,\ldots ,{x_{2\gamma +1}})$ by assigning $x_i=1$ if and only if edge i is in $\tau$, for $1\le i \le 2{\gamma }+1$. The cost of the tour $\tau$ with cost matrix $Q^{\prime }$ is precisely ${\mathbf {x}}^TQ{\mathbf {x}}$. Since QUBO is strongly NP-hard, the result follows. $\square$

Let us now examine the complexity of some special cases of QTSP restricted to DEE-tours. The problem QTSP(p, H) where the family of feasible solutions is restricted to DEE-tours on $G^*$ is called double edge ejection QTSP with rank p, and is denoted by QTSP(p, H)-DEE. We have the analogous definition for QTSP-DEE(p,c).

Theorem 3.2

QTSP(p, c)-DEE is NP-hard even if $p=1$ and $c(e)=0$ for all $e\in E$.

Proof

We reduce the PARTITION problem to QTSP(1, H)-DEE. From an instance of PARTITION with the given data $\alpha _1,\ldots ,{\alpha _\eta }$, construct an instance of QTSP(1, H)-DEE as follows.

For each $k=1,2,\ldots ,{\eta }$ create a 3-cycle C(k) on the vertex set $\{u_k,v_k,w_k\}$. Build the graph $G^*=(V,E)$ using these cycles. Introduce a weight for each edge $(i,j)\in E$ as follows: For $k=1,2,\ldots ,{\eta }$, assign weight $\alpha _k$ to edge $(v_k,u_k)$, $-\alpha _k$ to the edge $(v_k,w_k)$, and M to $(w_k,u_k)$, where $M= 1+{\eta }\left( \sum _{k=1}^\eta |\alpha _k|\right)$. The weights of the edges $(t,v_1), (t,u_1)$ and $(t,w_1)$ are $-\left( \sum _{k=1}^n\alpha _k\right) /4$. All other edges have weight zero. Let $a_{ij}$ denote the weight of edge (i, j) constructed above and choose another set of weight $b_{ij}$ which is the same as $a_{ij}$. Then the objective function of QTSP(1, H)-DEE on the $G^*$ constructed above becomes $\left( \sum _{(i,j)\in \tau }a_{ij}\right) ^2$, where $\tau$ is a DEE-tour in this $G^*$. It may be noted that from each 3-cycle C(k), two edges are to be ejected. In any optimal solution to the constructed instance of QTSP(1, H)-DEE, one of the ejected edges from each cycle must be the one with weight M. Thus for the other ejected edge, one needs to choose an edge with weight $\alpha _k$ or $-\alpha _k$. It can be verified that the optimal objective function value of this QTSP(1, H)-DEE is zero precisely when the required partition exists. The result follows from the NP-completeness of PARTITION (Karp 1972). $\square$

Fig. 7

Construction of the graph $G^*$ used in the proof of Theorem 3.2. Note that the dashed edges have weight $-\left( \sum _{k=1}^n\alpha _k\right) /4$

We now show that the QTSP(p, c)-DEE (and hence the QTSP(p, H)-DEE) can be solved in pseudopolynomial time and the problems admit FPTAS when the edge weights are non-negative. Our proof technique is to reduce QTSP(p, H)-DEE to QSPP(p, H) on a specially-constructed acyclic multigraph which we now describe (Fig. 7).

Given a $G^*$ graph construct the acyclic digraph $G^{\prime }$ as follows. Note that the vertex set $V^k$ of cycle C(k) in $G^*$ is represented by $V^k =\{v^k_1,v^k_2,\ldots ,v^k_{r_k}\}$. Also, the edge set of C(k) is $E(k) = \{e^k_1,e^k_2,\ldots ,e^k_{r_k}\}$, where $e^k_i = (v^k_i,v^k_{i+1})$ and the indices are taken modulo $r_k$. For $k=1,2,\ldots ,m-1$, create ${\hat{E}}(k) =\{{\hat{e}}^k_1, {\hat{e}}^k_2,\ldots ,{\hat{e}}^k_{r_k}\}$. ${\hat{E}}(k)$ can be viewed as a copy of E(k). Construct a graph $G^{\prime }=(V^{\prime },E^{\prime })$ where $V^{\prime }= \{t_1,t_2\}\cup E(m) \cup \left\{ {\bigcup \limits _{k=1}^{m-1}} (E(k)\cup {\hat{E}}(k))\right\}$. For each $k=1,2,\ldots ,m-1$ and $i,j=1,2,\ldots ,r_k$, introduce a directed arc $e=(e^k_i,{\hat{e}}^k_j), i\ne j$ and set 2p weights $\alpha ^h_{e}=C(a^h,k)-a^h_{e^k_i}-a^h_{e^k_j}$ and $\beta ^h_e= C(b^h,k)-b^h_{e^k_i}-b^h_{e^k_j}$ for $h=1,2,\ldots ,p$, where $C(a^h,k)=\sum _{e\in C(k)}a^h_e$ and $C(b^h,k)=\sum _{e\in C(k)}b^h_e$. The arc $e=(e^k_i,{\hat{e}}^k_j)$, $i\ne j$, represents the events of ejecting edges $e^k_i$ and $e^k_j$ from cycle C(k) where a Hamiltonian cycle “enters” C(k) through $e^k_i$ and “leaves” C(k) through $e^k_j$. For every $k=1,2,\ldots ,m-1$, $i=1,2,\ldots ,r_{k}$, and $j=1,2,\ldots ,r_{k+1}$, introduce two directed arcs $e_1=({\hat{e}}^k_i,e^{k+1}_j)$ and $e_2=({\hat{e}}^k_i,e^{k+1}_j)$. Note that $e_1$ and $e_2$ are parallel arcs in $G^{\prime }$ in the same direction. Let $u_1$ and $u_2$ be the endpoints of $e^k_i$ in $G^{*}$ and $v_1,v_2$ be the endpoints of $e^{k+1}_j$ in $G^*$. Now set the weights $\alpha ^h_{e_1}=a^h_{u_1v_1}+a^h_{u_2v_2}$ and $\beta ^h_e= b^h_{u_1v_2}+b^h_{u_2v_1}$ for $h=1,2,\ldots ,p$. The arc $e_1$ represents ejecting $e^k_i$ from C(k) and $e^{k+1}_j$ from $C(k+1)$ in $G^*$ and patching cycles using “non-cross edges”. The edge $e_2$ represents the same event but the patching is done using “cross edges” instead. The tip vertex $t_1$ is connected to $e^1_i$ for $i=1,2,\ldots ,r_1$. Set 2p weights for the arcs $e_i=(t, e^k_i)$ in $G^{\prime }$ as $\alpha ^h(e_i)= a^h_{(t,v_i)}+a^h_{(t,v_{i+1})}$, $\beta ^h(e_i)= b^h_{(t,v_i)}+b^h_{(t,v_{i+1})}$, $h=1,2,\ldots ,p$, where $e_i=(v_i,v_{i+1})$ in $G^*$. Finally, connect all the nodes $e^m_i$ for $i=1,2,\ldots ,r_m$, to $t_2$ and all the $\alpha$ and $\beta$ weights of these arcs are zero. The graph $G'$ constructed from the $G^*$ in Fig. 1 is shown in Fig. 8.

Fig. 8

$G'$ constructed from the graph $G^*$ given in Fig. 1

Theorem 3.3

From an optimal ($\epsilon$-optimal) solution of QSPP(p,H,G$'$), an optimal ($\epsilon$-optimal) solution to QTSP(p, H)-DEE can be recovered in linear time.

Proof

From the construction of $G'$, it can be verified that there is a one-to-one correspondence between SEE-tours in $G^*$ and $t_1-t_2$ paths in $G'$ that preserves the objective function values of the corresponding solutions of QTSP(p, H)-DEE and QSPP(p, H). Note that $G^{\prime }$ is an acyclic multigraph with at most two multiples of each edge. It is possible to use our algorithm for QSPP(p, H) (Algorithm 1) on an acyclic digraph for the multigraph case as well, and the result follows. $\square$

Now, from the construction above, and the results from the previous section, we immediately have the following.

Corollary 3.4

QTSP(p, H)-DEE can be solved in $O(mn^{2p+1}U)$ time, where $U=\prod _{h=1}^p \max _{e\in E} |a^h_e| \max _e |b^h_e|$, for any fixed p. Moreover, QTSP(p, H)-DEE admits an FPTAS when ${\mathbf {a}},{\mathbf {b}} \ge {\mathbf {0}}$.

The instance of QTSP(A) when the family of tours is restricted to F(DEE) is denoted by QTSP(A)-DEE. Our reduction of QTSP(p, H)-DEE to QSPP(p, H) discussed above cannot be applied directly to solve QTSP(A)-DEE. As before, the reduction can be modified to take into consideration the cost arising from adjacent pairs of edges to get an instance of adjacent QSPP(p, H) on an acyclic graph, and hence QTSP(A)-DEE can be solved in polynomial time. We present a simple $O(n^3)$ algorithm to solve QTSP(A)-DEE directly.

Every DEE-tour in $G^*$ is defined by the edges which are removed upon entering and exiting each cycle C(i), the edge which is removed from C(m), and the choice of matching between the endpoints of the edge removed when exiting C(i) and the edge removed when entering $C(i+1)$ for $i=1,\ldots ,m-1$. When two consecutive edges are removed from cycle C(i) (the edges which are removed from cycle C(i) share an endpoint v), the DEE-tour contains a path (u, v, w) where $u\in C(i-1)$ and $w\in C(i+1)$. That is, the quadratic costs which are incurred depend on the edges which are removed from $C(i-1)$ and $C(i+1)$ (as in the tour in Fig. 6). This prevents the approach used by Glover and Punnen (1997) for the linear TSP from being extended to QTSP(p, H)-DEE. This also complicates any dynamic programming approach which attempts to construct an optimal solution by considering one cycle in each iteration, however, we show that it still can be done by considering two consecutive cycles instead of one in a dynamic programming recursion.

Let $f^1(v^k_i, v^{k-1}_{j})$ and $f^2(v^k_i, v^{k-1}_{j})$ be the lengths of a smallest expanded cycle D(k) in $G^*$ containing edges $(v^k_i,v^{k-1}_{j})$, $(v^k_{i+1},v^{k-1}_{j+1})$, and $(v^k_i,v^{k-1}_{j+1})$, $(v^k_{i+1},v^{k-1}_{j})$, respectively, and let

$$\begin{aligned} g\left( v^k_i\right) = \sum _{s=1}^{r_k}q\left( v^k_s,v^k_{s+1},v^k_{s+2}\right) -q\left( v^k_i,v^k_{i+1},v^k_{i+2}\right) -q\left( v^k_{i-1},v^k_i,v^k_{i+1}\right) . \end{aligned}$$

In the above expression and that follows, we assume that the indices $r_k+1 \equiv 1, r_k+2 \equiv 2,$ and $0 \equiv r_k$. Let $h^1_1\left( v^k_i,v^{k-1}_{j}\right)$ represent the length of a smallest expanded cycle D(k) in $G^*$ containing edges $(v^k_i,v^{k-1}_{j})$ and $(v^k_{i+1},v^{k-1}_{j+1})$, that was not constructed by selecting two adjacent edges to eject from $C(k-1)$. That is,

$$\begin{aligned} h^1_1\left( v^k_i,v^{k-1}_{j}\right)&= q\left( v^k_{i},v^{k-1}_{j},v^{k-1}_{j-1}\right) + q\left( v^k_{i+1},v^{k-1}_{j+1},v^{k-1}_{j+2}\right) \\&\quad -q\left( v^{k-1}_{j-1},v^{k-1}_{j},v^{k-1}_{j+1}\right) - q\left( v^{k-1}_{j},v^{k-1}_{j+1},v^{k-1}_{j+2}\right) \\&\quad +\min _{\begin{array}{c} 1\le s \le r_{k-1},\\ s\not \in \{ j-1,j,j+1\} \\ 1\le t\le r_{k-2} \end{array}} \left\{ f^1(v_s^{k-1},v_t^{k-2}),f^2(v_s^{k-1},v_t^{k-2}) \right\} . \end{aligned}$$

Let $h^1_2\left( v^k_i,v^{k-1}_{j}\right)$ represent the length of a smallest expanded cycle D(k) containing edges $(v^k_i,v^{k-1}_{j})$ and $(v^k_{i+1},v^{k-1}_{j+1})$, that was constructed by selecting edge $(v^{k-1}_{j+1},v^{k-1}_{j+2})$ when constructing $D(k-1)$ and $(v^{k-1}_j,v^{k-1}_{j+1})$ when constructing D(k). That is,

$$\begin{aligned} h^1_2\left( v^k_i,v^{k-1}_{j}\right)&= {q\left( v^k_{i},v^{k-1}_{j},v^{k-1}_{j-1}\right) - q\left( v^{k-1}_{j-1},v^{k-1}_{j},v^{k-1}_{j+1}\right) } \\&\quad + \min _{1\le t\le r_{k-2}} \{ f^1(v^{k-1}_{j+1},v^{k-2}_{t}) + q(v^{k}_{i+1},v^{k-1}_{j+1},v^{k-2}_{t}) \\&\quad - q(v^{k-1}_{j},v^{k-1}_{j+1}, v^{k-2}_{t}), \\&\quad f^2(v^{k-1}_{j+1},v^{k-2}_{t}) + q(v^{k}_{i+1},v^{k-1}_{j+1},v^{k-2}_{t+1}) - q(v^{k-1}_{j},v^{k-1}_{j+1},v^{k-2}_{t+1}) \}. \end{aligned}$$

Similarly, let $h^1_3\left( v^k_i,v^{k-1}_{j}\right)$ represent the length of a smallest expanded cycle D(k) containing edges $(v^k_i,v^{k-1}_{j})$ and $(v^k_{i+1},v^{k-1}_{j+1})$, that was constructed by selecting edge $(v^{k-1}_{j-1},v^{k-1}_{j})$ when constructing $D(k-1)$ and $(v^{k-1}_j,v^{k-1}_{j+1})$ when constructing D(k). That is,

$$\begin{aligned}&h^1_3\left( v^k_i,v^{k-1}_{j}\right) \\&\quad = {q\left( v^k_{i+1},v^{k-1}_{j+1},v^{k-1}_{j+2}\right) - q\left( v^{k-1}_{j},v^{k-1}_{j+1},v^{k-1}_{j+2}\right) }\\&\quad \quad + \min _{1\le t\le r_{k-2}} \{ f^1(v^{k-1}_{j-1},v^{k-2}_{t}) + q(v^{k}_{i},v^{k-1}_{j},v^{k-2}_{t+1}) - q(v^{k-1}_{j+1},v^{k-1}_{j}, v^{k-2}_{t+1}), \\&\quad \quad f^2(v^{k-1}_{j-1},v^{k-2}_{t}) + q(v^{k}_{i},v^{k-1}_{j},v^{k-2}_{t}) - q(v^{k-1}_{j+1},v^{k-1}_{j},v^{k-2}_{t}) \} . \end{aligned}$$

Then for $k=3,4,\ldots ,m$,

$$\begin{aligned} f^1\left( v^k_i,v^{k-1}_{j}\right)&= g(v^k_i) + q(v^{k}_{i-1},v^{k}_{i},v^{k-1}_{j}) + q(v^{k}_{i+2},v^{k}_{i+1},v^{k-1}_{j+1}) \\&\quad + \min \{ h^1_1\left( v^k_i,v^{k-1}_{j}\right) , h^1_2\left( v^k_i,v^{k-1}_{j}\right) , h^1_3\left( v^k_i,v^{k-1}_{j}\right) \}. \end{aligned}$$

Similar expressions follow for $h^2_1\left( v^k_i,v^{k-1}_{j}\right)$, $h^2_2\left( v^k_i,v^{k-1}_{j}\right)$, $h^2_3\left( v^k_i,v^{k-1}_{j}\right)$ and $f^2\left( v^k_i,v^{k-1}_{j}\right)$ using the cross-edges instead. The values of $f^1\left( v^2_i,v^1_{j}\right)$ and $f^2\left( v^2_i,v^1_{j}\right)$ for $1\le i\le r_2$ and $1\le j\le r_1$ can be calculated directly to initiate the above recursion. Thus, we can compute the value of a smallest expanded cycle D(i) for $i=1,2,\ldots ,r_m$. Note that the values for the expressions for $h^1_1(v^k_i,v^{k-1}_j)$ and $h^2_1(v^k_i,v^{k-1}_j)$ can be computed in $O(n^2)$ time for any k. The values for $h^1_2\left( v^k_i,v^{k-1}_{j}\right)$, $h^1_3\left( v^k_i,v^{k-1}_{j}\right)$, $h^2_2\left( v^k_i,v^{k-1}_{j}\right)$ and $h^2_3\left( v^k_i,v^{k-1}_{j}\right)$ can be computed in O(n). The values for $f^1\left( v^k_i,v^{k-1}_{j}\right)$ and $f^2\left( v^k_i,v^{k-1}_{j}\right)$ can then be computed in constant time, for each k. That is, the value of D(m) can be computed in $O(n^3)$ time. The foregoing discussions can be summarized in the theorem below (Figs. 9, 10, 11).

Theorem 3.5

QTSP(A)-DEE can be solved in $O(n^3)$ time.

Fig. 9

An example of an optimal expanded cycle D(3). The cost can be computed as $f^2(v^3_2,v^2_1)=f^1(v^2_2,v^1_2) + g(v^3_2) + q(v^3_2,v^2_2,v^1_2) + q(v^3_1,v^3_2,v^2_2) + q(v^3_4,v^3_3,v^2_1) + q(v^3_3,v^2_1,v^2_3) - q(v^2_1,v^2_2,v^2_3) - q(v^2_2,v^2_1,v^2_3)$. Note that some of the quadratic costs may contain vertices in 3 consecutive partitions of $G^*$, such as $q(v_2^1,v^2_2,v^3_2)$

4 Paired vertex graphs

We now consider a class of undirected graphs which contains an exponential number of tours but on which the linear TSP is solvable in O(n) time. Let $G^{p}=(V,E)$ be constructed as follows. Consider the sets $V^1,V^2,\ldots , V^\frac{n}{2}$ of pairs of vertices. For each vertex in $V^k$, add an edge connecting it to every vertex in $V^{k+1}$, for all $k=1,2,\ldots ,\frac{n}{2}-1$. Add an edge connecting the two vertices in $V^1$ to each other, and the two vertices in $V^\frac{n}{2}$ to each other. For $G^p$ with an odd number of vertices, a vertex can be added on the edge contained in $V^1$ and all following results hold. We note that although this graph class is similar to the graph $G^*$, it is not a special case of $G^*$ and, to the best of our knowledge, has not been previously studied in connection with the linear TSP.

Fig. 10

Example of $G^p$ on 12 vertices

Let F(PV) be the family of all tours which belong to $G^{p}$. It can be verified that $|F(PV)|=2^{n/2-1}$.

Theorem 4.1

The linear TSP on $G^p$ can be solved in O(n) time.

Proof

Let $G^p$ be a paired vertex graph on $2r=n$ vertices. Every tour $\tau$ in $G^p$ contains the edges $(v_1,v'_1)$ and $(v_r,v'_r)$. To connect $V^k$ to $V^{k+1}$, $\tau$ must either contain pairs of edges $(v_k,v_{k+1})$ and $(v'_k,v'_{k+1})$, or $(v_k,v'_{k+1})$ and $(v'_k,v_{k+1})$. It is now clear that $\tau ^*$ can be constructed greedily by adding pairs of edges joining vertices in $V^k$ to vertices in $V^{k+1}$ which minimize $\{c(v_k,v_{k+1}) + c(v'_k,v'_{k+1}), c(v_k,v'_{k+1}) + c(v'_k,v_{k+1})\}$ for each $k=1,\ldots ,r-1$. $\square$

Interestingly, the convex hull of the incidence vectors of tours in F(PV) has a compact representation. We give a linear description of the polytope $P(G^p)$ defined by the convex hull of the incidence vectors of tours of $G^p$.

Theorem 4.2

$$\begin{aligned} P(G^p)= & {} \{ {\mathbf {x}}\in \mathbb {R^E}: 0\le x_e\le 1 \text { for all } e\in E, \end{aligned}$$

(2)

$$\begin{aligned}&x_{u_1,v} + x_{u_2,v}=1:u_1,u_2\in V^{k-1},v\in V^k, \text { for all } k=2,\ldots ,\frac{n}{2}, \end{aligned}$$

(3)

$$\begin{aligned}&x_{u_1,v} + x_{u_2,v}=1:v\in V^k,u_1,u_2\in V^{k+1}, \text { for all } k=1,\ldots ,\frac{n}{2}-1, \end{aligned}$$

(4)

$$\begin{aligned}&x_{u,v}=1: u,v\in V^1, \end{aligned}$$

(5)

$$\begin{aligned}&x_{u,v}=1: u,v\in V^\frac{n}{2} \}. \end{aligned}$$

(6)

Proof

Let A be the coefficient matrix for $P(G^p)$ and $\tau$ be the tour with characteristic vector ${\mathbf {x}}$. Adding (3) and (4) implies that every vertex in $V^2,V^3,\ldots ,V^{n/2-1}$ has degree 2 in $\tau$. Since every edge in $G^p$ other than the edges contained in $V^1$ and $V^{n/2}$ connects vertices in successive partitions, a solution that contains a subtour must also include both edges incident with $v\in V^k$ and the vertices in $V^{k+1}$ (or $V^{k-1}$). This contradicts either (3) or (4), and thus, $\tau$ is a tour in $G^p$.

A is a binary matrix with exactly two ones in each row. Moreover, since the variable for every edge is in exactly two constraints, there are exactly two 1’s in each column. It follows that the coefficient matrix is totally unimodular, and hence $P(G^p)$ is a linear description of the polytope. $\square$

The variant of QTSP when the tours are restricted to PV-tours is denoted QTSP-PV.

Theorem 4.3

QTSP-PV is strongly NP-hard.

Proof

We reduce QUBO to QTSP-PV. From an instance of QUBO on ${\gamma }$ variables, we construct an instance of QTSP-PV as follows. Let $G^p$ be a graph on ${\gamma }+1$ pairs of vertices, $V(G^p)={\bigcup \limits _{k=1}^{\gamma +1}} V^k$, where $V^k=\{v_k,v'_k\}$. $G^p$ contains edges connecting each vertex in $V^k$ to each vertex in $V^{k+1}$ for each $k=1,2,\ldots ,{\gamma }$, an edge connecting the vertices in $V^1$, as well as an edge connecting the vertices of $V^{n+1}$. Assign costs $q((v_i,v_{i+1}),(v_j,v_{j+1}))=Q_{ij}$ for all $i,j{=1,2,\ldots ,{\gamma }}$. For all other pairs of edges (e, f) in $G^p$, assign $q(e,f)=0$.

Given any solution ${\mathbf {x}}= (x_1,x_2,\ldots ,{x_\gamma })$ of QUBO, we can construct a tour $\tau$ in $G^p$ containing the edges $(v_i,v_{i+1})$ and $(v'_i,v'_{i+1})$ if $x_i=1$ and the edges $(v_i,v'_{i+1})$ and $(v'_{i},v_{i+1})$ if $x_i=0$, for $1\le i\le {\gamma }$, as well as the edges contained in $V^1$ and $V^{n+1}$. It can be verified that the cost of $\tau$ is precisely ${\mathbf {x}}^TQ{\mathbf {x}}$.

Conversely, given any tour $\tau$ in the graph $G^p$ obtained above, construct a vector ${\mathbf {x}}$ as $x_i=1$ if and only if edge $(v_i,v_{i+1})$ belongs to $\tau$. The cost of the tour $\tau$ is precisely ${\mathbf {x}}^TQ{\mathbf {x}}$. Since QUBO is strongly NP-hard, the result follows. $\square$

Fig. 11

Example of a tour $\tau$ in $G^p$ which corresponds to the solution ${\mathbf {x}}=(1,0,0,1,1)$ in the proof of Theorem 4.3

The problem QTSP(p, H) where the family of feasible solutions is restricted to PV-tours is called the paired vertex QTSP with rank p and is denoted by QTSP(p, H)-PV. We have the analogous definition for QTSP(p, c).

Theorem 4.4

QTSP(p, c)-PV is NP-hard even when $p=1$ and $c(e)=0$ for all $e\in E$.

Proof

We reduce the PARTITION problem to QTSP(1, H)-PV. From an instance of PARTITION with the given data $\alpha _1,\ldots ,{\alpha _\eta }$, we construct an instance of QTSP(1, H)-PV as follows. Let $G^p$ be a graph on ${\eta }+1$ pairs of vertices, $V(G^p)={\bigcup \limits _{k=1}^{\eta +1}} V^k$, where $V^k=\{v_k,v'_k\}$. $G^p$ contains edges connecting each vertex in $V^k$ to each vertex in $V^{k+1}$ for each $k=1,2,\ldots ,{\eta }$, an edge connecting the vertices in $V^1$, as well as an edge connecting the vertices of ${V^{\eta +1}}$. Assign costs $a(v_i,v_{i+1})=b(v_i,v_{i+1})=\alpha _i$ and $a(v_i,v'_{i+1})=b(v_i,v'_{i+1})=-\alpha _i$ for each $i=1,2,\ldots ,{\eta }$. The objective function of QTSP(1, H)-PV on the $G^p$ constructed above becomes $(\sum _{e\in \tau }a_e)^2 \ge 0$, where $\tau$ is a tour in this $G^p$. It can be verified that the optimal objective function value of this QTSP(1, H)-PV is zero precisely when the required PARTITION exists. We refer the reader to Fig. 12. The result follows from the NP-completeness of PARTITION (Karp 1972). $\square$

Fig. 12

Example of a tour $\tau$ in $G^p$ which corresponds to the solution $S=\{1,4,5\}$ in the proof of Theorem 4.4

Despite this negative result, we now show that when p is fixed, QTSP(p, H)-PV can be solved in pseudopolynomial time and in this case it also admits an FPTAS when the edge weights are nonnegative. Recall that an instance of QTSP(p, H)-PV is given by p pairs of costs $a^r_{ij},b^r_{ij}$ for $r=1,2,\ldots ,p$, for each edge $(i,j)\in G^p$. We formulate QTSP(p, H) as a rank p quadratic shortest path problem in an acyclic directed graph.

Given a graph $G^p$, construct the acyclic digraph $G'$ as follows. Note that the vertex sets in $G^p$ are $V^k=\{v_k,v'_k\}$ for $k=1,2,\ldots , \frac{n}{2}$. Construct graph $G'=(V',E')$ where $V'=\{{\hat{v}}_1,{\hat{v}}_2\ldots ,{\hat{v}}_{n/2}\}$. For each pair of edges $(v_k,v_{k+1})$ and $(v'_k,v'_{k+1})$ in $G^p$, introduce a directed arc $e_k=({\hat{v}}_k,{\hat{v}}_{k+1})$ which represents the edges $(v_k,v_{k+1})$ and $(v'_k,v'_{k+1})$ being included in a Hamiltonian cycle, and similarly, for each pair of edges $(v_k,v'_{k+1})$ and $(v'_k,v_{k+1})$ in $G^p$, introduce a directed arc ${\bar{e}}_k=({\hat{v}}_k,{\hat{v}}_{k+1})$. For $h=1,2,\ldots ,p$, set $\alpha ^h_{e_1}=a^h_{v_1,v'_1} + a^h_{v_1,v_2} + a^h_{v'_1,v'_2} + a^h_{v_k,v'_k}$, $\alpha ^h_{{\bar{e}}_1}=a^h_{v_1,v'_1} + a^h_{v_1,v'_2} + a^h_{v'_1,v_2} + a^h_{v_k,v'_k}$, $\beta ^h_{e_1}=b^h_{v_1,v'_1} + b^h_{v_1,v_2} + b^h_{v'_1,v'_2} + b^h_{v_k,v'_k}$, and $\beta ^h_{{\bar{e}}_1}=b^h_{v_1,v'_1} + b^h_{v_1,v'_2} + b^h_{v'_1,v_2} + b^h_{v_k,v'_k}$. For $k=2,3\ldots ,n/2-1$, and $h=1,2,\ldots ,p$ we set $\alpha ^h_{e_k}=a^h_{v_k,v_{k+1}} + a^h_{v'_k,v'_{k+1}}$, $\alpha ^h_{{\bar{e}}_k}=a^h_{v_k,v'_{k+1}} + a^h_{v'_k,v_{k+1}}$, $\beta ^h_{e_k}=b^h_{v_k,v_{k+1}} + b^h_{v'_k,v'_{k+1}}$ and $\beta ^h_{{\bar{e}}_k}=b^h_{v_k,v'_{k+1}} + b^h_{v'_k,v_{k+1}}$. The graph $G'$ constructed from the $G^p$ in Fig. 12 is shown in Fig. 13.

Fig. 13

$G'$ constructed from the graph $G^p$ given in Fig. 12

Let $\Pi$ be the collection of a paths from ${\hat{v}}_1$ to ${\hat{v}}_{n/2}$ in $G'$. From the construction given above, it can be verified that there is a one-to-one correspondence between elements of $\Pi$ and elements of F(PV) where the corresponding elements have the same weight. Further, given an element of $\Pi$, we can construct a corresponding element in F(PV) in polynomial time. Note that the graph $G^{\prime }$ is an acyclic multigraph with exactly two multiples of each edge. Thus, QTSP(p, H)-PV can be solved in pseudopolynomial time, and a minor modification of the analysis in the proof of Theorem 2.5 yields the following theorem. Although the number of edges doubles, this does not change the worst-case complexity.

Corollary 4.5

QTSP(p, H)-PV can be solved in $O(n^{2p+1}U)$ time, where $U=\prod _{h=1}^p (\max _{e\in E} |a^h_e| \max _e |b^h_e|)$, for any fixed p. Moreover, QTSP(p, H)-PV admits an FPTAS when ${\mathbf {a}},{\mathbf {b}} \ge {\mathbf {0}}$.

We now show that the adjacent quadratic TSP restricted to the set of paired vertex tours, denoted QTSP(A)-PV, can be solved in polynomial time using dynamic programming. The input for QTSP(A)-PV is given as the costs of paths of length two in $G^p$. That is, for any 2-path $u-v-w$ with v as the middle vertex, a cost q(u, v, w) is given. Note that $q(u,v,w)=q(w,v,u)$. Let f(k) be the length of a smallest PV-Hamiltonian path in $G^p$ from $v_k$ to $v'_k$ containing the edges $(v_{k-1},v_k)$ and $(v'_{k-1},v'_k)$. Similarly, let g(k) be the length of a smallest PV-Hamiltonian path containing $(v_{k-1},v'_{k})$ and $(v'_{k-1},v_k)$. Then for $k=2,3,\ldots ,\frac{n}{2}-1$,

$$\begin{aligned} f(k+1)&= \min \{ f(k) + q(v_{k-1},v_k,v_{k+1}) + q(v'_{k-1},v'_k,v'_{k+1}),\\&\quad g(k) + q(v_{k-1},v'_k,v'_{k+1}) + q(v'_{k-1},v_k,v_{k+1})\} \}, \end{aligned}$$

and

$$\begin{aligned} g(k+1)&= \min \{ f(k) + q(v_{k-1},v_k,v'_{k+1}) + q(v'_{k-1},v'_k,v_{k+1}), \\&\quad g(k) + q(v_{k-1},v'_k,v_{k+1}) + q(v'_{k-1},v_k,v'_{k+1})\} \}. \end{aligned}$$

The values of f(2) and g(2) can be calculated directly to initiate the recursion. Adding the edge $(v_{\frac{n}{2}},v'_{\frac{n}{2}})$ completes the tour and the better of the two tours gives an optimal solution to QTSP(A) on $G^p$. The foregoing discussion can be summarized in the theorem below.

Theorem 4.6

QTSP(A)-PV can be solved in O(n) time.

The results discussed in this section can easily be modified to obtain corresponding results when n is odd by adding a single vertex $v_1''$ along the edge $(v_1,v_1')$. Then, every tour which contains $(v_1,v_1')$ will contain edges $(v_1,v_1'')$ and $(v_1',v_1'')$ in the modified graph, and the results for the case when n is odd follow immediately.

5 Matching edge ejection tours

In this section we consider a special class of tours considered by Punnen (2001b). Consider a special spanning subgraph $G^M$ of the complete graph $K_n$ obtained as follows. Partition the vertices of $K_n$ into two sets, $U=\{u_1,u_2,\ldots ,u_r\}$ and $V=\{v_1,v_2,\ldots ,v_s\}$. Let $E_u=\{(u_i,u_{i+1}):1\le i\le r\}$, where $r+1\equiv 1$ and $E_{uv}=\{(u_i,v_j):1\le i\le r, 1\le j\le s\}$. Hereafter, we assume that $s\le r$. The edge set of $G^M$ is defined as $E(G^M)=E_u\cup E_{uv}$. The resulting graph is denoted by $G^M=(V^M,E^M)$ (see Fig. 14 for an example of a $G^M$ graph), where $V^M=U\cup V$.

Fig. 14

A graph $G^M$ with $r=6$ and $s=4$

Since the TSP is NP-hard on a complete bipartite graph and $G^M$ has a spanning subgraph which is a complete bipartite graph, the TSP is NP-hard on $G^M$ as well. Let us now consider a family of tours in $G^M$, called matching edge ejection tours (MEE-tours) which consists of all tours in $G^M$ that can be obtained by the following process.

• (1) Eject s edges $e_{\pi (1)},e_{\pi (2)},\ldots ,e_{\pi (s)}$ from the cycle $E_u\equiv (u_1,u_2,\ldots ,u_r,u_1)$, and let $E_u(s)=E_u - \{e_{\pi (1)},e_{\pi (2)},\ldots ,e_{\pi (s)}\}$ be the edge set of the resulting subgraph.

• (2) Insert the vertices $v_i\in V$ into $E_u(s)$ by connecting it by edges to the endpoints of $e_{\pi (i)}$, $1\le i\le s$ to construct a tour in $G^M$ (see Fig. 15 for an MEE-tour in the $G^M$ graph of Fig. 14).

Fig. 15

An MEE-tour in the graph $G^M$ given in Fig. 14

Let F(MEE) be the collection of all MEE-tours in $G^M$. It has been shown in Punnen (2001b) that $|F(MEE)|=\frac{r!}{(r-s)!}$. If n is even and $r=n/2$, then $|F(MEE)|=(\frac{n}{2})!$, and if n is odd and $r=(n+1)/2$, then $|F(MEE)|=(\frac{n+1}{2})!$. In fact, |F(MEE)| could be even larger than $(\frac{n}{2})!$ for an appropriate choice of r and s. Gutin (1999) showed that |F(MEE)| could be as large as $(\frac{n}{2} + p_0)!/(2p_0)!$ where $p_0=\sqrt{\frac{1}{8}(n+\frac{9}{8})} + \frac{3}{8}$. Finding the best QTSP tour in F(MEE) is a nontrivial task. Interestingly, TSP restricted to MEE-tours can be solved in $O(n^3)$ time by formulating it as a minimum weight perfect matching problem on an associated bipartite graph (Punnen 2001b).

The quadratic travelling salesman problem where the family of feasible solutions is restricted to MEE-tours is denoted by QTSP-MEE. Note that by using the rank decomposition of the matrix Q (which has rank p), QTSP-MEE can be stated as

$$\begin{aligned} \text {Minimize } q(\tau )&= \sum _{h=1}^p\left( \sum _{e\in \tau } a_e^h\right) \left( \sum _{e\in \tau }b_e^h\right) \\&\quad \text {Subject to } \tau \in F(SEE). \end{aligned}$$

It may be noted that in the above representation, p could be $O(n^2)$.

QTSP-MEE is strongly NP-hard. This follows directly from a stronger result that we later prove.

The quadratic assignment problem on the complete bipartite graph $G'=(U,V,E)$ which, by using the rank decomposition, can be stated as

$$\begin{aligned}&QAP(G'): \text {Minimize } q(P) = \sum _{h=1}^p \left( \sum _{e\in P}\alpha ^h_e\right) \left( \sum _{e\in P}\beta ^h_e\right) \\&\quad \text {Subject to } P \in {\mathcal {P}}, \end{aligned}$$

where ${\mathcal {P}}$ is the set of all perfect matchings in $G'$, and $|U|=|V|=n$. When n is odd, we denote QAP(G$'$) as odd-QAP. It is easy to see that odd-QAP is strongly NP-hard.

By extending the formulation (Punnen 2001b), we can also formulate QTSP-MEE as a QAP(G$'$).

Given a graph $G^M$, construct the complete bipartite graph $G'$ as follows. Note that the vertex set of $G^M$ is represented by $V^M=U\cup V$ where $U=\{u_1,u_2,\ldots ,u_r\}$ and $V=\{v_1,v_2,\ldots ,v_s\}$. Also, the edge set is $E(G^M)=E_u\cup E_{uv}$ where $E_u=\{e_i=(u_i,u_{i+1}):1\le i\le r\}$ and $E_{uv}=\{(u_i,v_j):1\le i\le r, 1\le j\le s\}$, $r+1\equiv 1$ and $s\le r$. Construct a complete bipartite graph $G'=(V',E')$ where $V'=\{E_u \cup (V \cup \{v_i:s<i\le r\}) \}$ and $E'=\{(e_i,v_j):e_i\in E_u,v_j\in V \cup \{v_i:s<i\le r\}\}$. For $j\in V$ set weights $\alpha _{ij}^h=a_{u_i,v_j}^h + a_{v_j,u_{i+1}}^h - a_{u_i,u_{i+1}}^h$ and $\beta ^h_{ij}=b_{u_i,v_j}^h + b_{v_j,u_{i+1}}^h - b_{u_i,u_{i+1}}^h$, and set weights $\alpha _{ij}^h=a_{u_i,u_{i+1}}^h$ and $\beta ^h_{ij}=b_{u_i,u_{i+1}}^h$, otherwise, for all $h=1,2,\ldots ,p$ and all i such that $e_i\in E_u$. For $j\le s$, the edge $e=(e_i,v_j)$ represents the events of ejecting edge $e_i$ from cycle $E_u$ and inserting $v_j$ by joining it to the endpoints of $e_i$, otherwise e represents the event that no vertex is inserted along $e_i$.

The problem QTSP(p, c) restricted to the collection of tours in F(MEE) is denoted QTSP(p, c)-MEE. We have the analogous definition for the homogenous case, denoted QTSP(p, H)-MEE.

Corollary 5.1

QTSP(p, c)-MEE is NP-hard even if $p=1$ and $c(e)=0$ for all $e\in E^M$.

The proof follows from the reduction above using the fact that rank 1 odd QAP is NP-hard (Punnen 2001a).

Corollary 5.2

QTSP(1, H)-MEE admits an FPTAS when ${\mathbf {a}},{\mathbf {b}}\ge {\mathbf {0}}$.

The proof of this corollary follows from the reduction given above and applying the result of Goyal et al. (2011) on the resulting rank 1 odd QAP.

The adjacent quadratic TSP over the collection of MEE-tours is denoted QTSP(A)-MEE. Note that QTSP(A)-SEE, QTSP(A)-DEE, and QTSP(A)-PV are solvable in polynomial time. This simplicity however, does not extend to QTSP(A)-MEE.

Theorem 5.3

QTSP(A)-MEE is strongly NP-hard.

Proof

We give a reduction from the linear TSP. Given a graph G on the vertices $1,2,\ldots ,n$, and linear cost function c defined on the edges of G, the graph $G^M$ is constructed on the vertex set $V^M=U\cup V$, where $U=\{u_1,u_2,\ldots , u_n\}$ and $V=\{v_1,v_2,\ldots , v_n\}$. Let $E_u$ be the cycle $(u_1,u_2,\ldots ,u_n,u_1)$. The indices are taken modulo n. For an illustration of this construction, see Fig. 16. Assign quadratic cost on the pairs of adjacent edges $q((u_i,v_j),(v_j,u_k))=c(i,k)$ for $i,j,k=1,2,\ldots ,n$, $i\ne k$. All other costs are zero.

Fig. 16

Construction used in the proof of Theorem 5.3

It can be verified that every tour $\pi =(\pi (1),\pi (2),\ldots ,\pi (n),\pi (1))\in G$ has the same cost as the tour $\pi '$ which results from inserting $\pi (i)$ into edge $(u_i,u_{i+1})$, for each $i=1,2,\ldots ,n$, that is, $\pi '=(u_1,v_{\pi (1)},u_2,v_{\pi (2)},\ldots ,u_n,v_{\pi (n)},u_1)\in G'$ (see Fig. 17). This establishes a one-to-one correspondence between tours in G and MEE-tours in $G^M$, and the result follows. $\square$

Fig. 17

An example of the construction used in the proof of Theorem 5.3, with $n=7$, is shown. The solid lines indicate the tour $\pi '\in G'$ defined by $\pi \in G$. The cycle $E_u=(u_1,u_2,\ldots ,u_7,u_1)$ is shown with dashed lines

6 Conclusion

We presented a systematic study of various complexity aspects of QTSP which generalizes the well-known travelling salesman problem. We have shown that QTSP is NP-hard on several classes of exponential neighbourhoods for which the linear TSP is polynomially-solvable. We introduce a restricted version of the QTSP objective, the fixed-rank QTSP, and examine the complexity of this problem on these classes of exponential neighbourhoods. It is shown that QTSP(p, c)-SEE, QTSP(p, c)-DEE, and QTSP(p, c)-PV can be solved in pseudopolynomial time and they also admit an FPTAS. QTSP(p, c)-MEE with $p=1$ can be solved in pseudopolynomial time and admits an FPTAS. For fixed $p>1$, the complexity status is open. For the adjacent QTSP variation, i.e. QTSP(A)-SEE, QTSP(A)-DEE and QTSP(A)-PV, we present polynomial algorithms. The problem QTSP(A)-MEE is shown to be strongly NP-hard. As a by-product, we obtain an FPTAS for the fixed-rank quadratic shortest path problem, and a pseudopolynomial algorithm when the problem is restricted to acyclic graphs.