Erratum: The Travelling Salesman and the PQ-Tree

Let D=(d_ij) be the n×n distance matrix of a set of n cities {1,2,…,n}, and let T be a PQ-tree with node degree bounded by d that represents a set Π(T) of permutations over {1,2,…,n}. We show how to compute for D in O(2^dn³) time the shortest travelling salesman tour contained in Π(T). Our algorithm may be interpreted as a common generalization of the well-known Held and Karp dynamic programming algorithm for the TSP and of the dynamic programming algorithm for finding the shortest pyramidal TSP tour.

A consequence of our result is that the shortcutting phase of the “twice around the tree” heuristic for the Euclidean TSP can be optimally implemented in polynomial time. This contradicts a statement of Papadimitriou and Vazirani as published in 1984.