<p>The quadratic traveling salesperson problem takes as input a graph and a cost for each pair of edges, and asks for a Hamiltonian cycle minimizing the sum of costs of its pairs of edges (not just adjacent pairs). It is NP-hard on Halin graphs (so its decision problem is NP-complete on all graphs of treewidth 3); see:</p>
<p>Brad Woods, Abraham Punnen, and Tamon Stephen (2017), &quot;A linear time algorithm for the 3-neighbour Travelling Salesman Problem on a Halin graph and extensions&quot;, <em>Discrete Optimization</em> 26: 163–182, <a href="https://doi.org/10.1016/j.disopt.2017.08.005" rel="noreferrer">doi:10.1016/j.disopt.2017.08.005</a></p>
<p>However it is trivially solvable in polynomial time on series-parallel graphs because they are only Hamiltonian if they are biconnected outerplanar and in that case the Hamiltonian cycle is unique (it is the outer face of the outerplanar embedding).</p>

CC BY-SA 4.0
2022-10-12T07:06:59.457Z
Thank you so much. This result is amazing.
Yuhang Bai
CC BY-SA 4.0
2022-10-11T06:06:02.570Z
2022-10-11T06:06:02.570Z
David Eppstein
<p>Whether there is a problem to meet the conditions: it is polynomial time solvable in series parallel graphs but NP-hard in graph with bounded treewidth?</p>

<np-hardness><treewidth>
Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth
Yuhang Bai
# Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth

(Asked by: username_0 on 2022-10-07)

Whether there is a problem to meet the conditions: it is polynomial time solvable in series parallel graphs but NP-hard in graph with bounded treewidth?

**Tags:** np-hardness, treewidth


---

## 1 answers

### Answer by username_1 on 2022-10-11. Score: 10 | Accepted answer

The quadratic traveling salesperson problem takes as input a graph and a cost for each pair of edges, and asks for a Hamiltonian cycle minimizing the sum of costs of its pairs of edges (not just adjacent pairs). It is NP-hard on Halin graphs (so its decision problem is NP-complete on all graphs of treewidth 3); see:

Brad Woods, Abraham Punnen, and Tamon Stephen (2017), "A linear time algorithm for the 3-neighbour Travelling Salesman Problem on a Halin graph and extensions", *Discrete Optimization* 26: 163–182, [doi:10.1016/j.disopt.2017.08.005](https://doi.org/10.1016/j.disopt.2017.08.005)

However it is trivially solvable in polynomial time on series-parallel graphs because they are only Hamiltonian if they are biconnected outerplanar and in that case the Hamiltonian cycle is unique (it is the outer face of the outerplanar embedding).

> **Comments:**
> **username_0**: Thank you so much. This result is amazing.  

---

