  We consider the linearization problem associated with the quadratic traveling
salesman problem (QTSP). Necessary and sufficient conditions are given for a
cost matrix $Q$ of QTSP to be linearizable. It is shown that these conditions
can be verified in $O(n^5)$ time. Some simpler sufficient conditions for
linearization are also given along with related open problems.

Discrete Mathematics;Computational Complexity