3
$\begingroup$

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?

$\endgroup$

1 Answer 1

10
$\begingroup$

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

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).

$\endgroup$
1
  • $\begingroup$ Thank you so much. This result is amazing. $\endgroup$
    – zhukui bai
    Oct 12, 2022 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.