The complexity of the longest tour through points in the plane

The shortest tour through $n$ points in the plane is NP-hard to find. The longest tour behaves differently: with Manhattan distances it takes linear time, and with Euclidean distances in three dimensions it is NP-hard. For Euclidean distances in the plane, its complexity is unknown.

Problem

Maximum TSP in the Euclidean plane. Given $n$ points $p_1,\dots,p_n\in\mathbb{Q}^2$, find a tour, that is, a cyclic order $\sigma$ of the points, maximizing the total length

$$\sum_{i=1}^{n}\big\|p_{\sigma(i)}-p_{\sigma(i+1)}\big\|_2, \qquad \sigma(n+1)=\sigma(1).$$

Question. What is the complexity of this problem? In particular, is it NP-hard (in the sense that deciding whether a tour longer than a given rational bound exists is NP-hard), or can it be solved in polynomial time?

The decision version is not even known to be in NP, because comparing a sum of Euclidean distances with a bound is the sum of square roots problem.

Background

Barvinok, Fekete, Johnson, Tamir, Woeginger and Woodroofe studied the maximum TSP for points in $\mathbb{R}^d$ under various norms and found that its complexity depends on the shape of the unit ball rather than on the combinatorics [1]. They closed with the conjecture that the planar Euclidean case is NP-hard, noting that local gadget arguments are harder to use for maximization problems. The earliest known mention of the problem is Barvinok's 1996 paper [2], and Fekete (1999) conjectured NP-hardness; it is Problem 49 of The Open Problems Project, as a test of how the complexity of a natural problem depends on the geometry of distances.

What is known

• Approximation. For every fixed dimension and every $L_p$ or polyhedral norm, the maximum TSP has a polynomial-time approximation scheme (Serdyukov; Barvinok, 1996) [2].
• Polyhedral norms are easy. If the unit ball is a polytope with $f$ facets, a maximum tour can be found in $O(n^{f-2}\log n)$ time, and in $O(n)$ time for the rectilinear and maximum norms in the plane [1], [3].
• Euclidean distances are hard in 3D. The maximum TSP with Euclidean distances is NP-hard in $\mathbb{R}^d$ for every fixed $d\ge 3$, and also for points on a sphere [1].
• Contrast. The minimum TSP is NP-hard in every fixed dimension for every $L_p$ or polyhedral norm, including the Euclidean plane [1].
• A relative. The maximum scatter TSP, which maximizes the shortest edge of the tour, is NP-hard in dimension 3 and higher (Fekete, 1999) and also open in the plane.

What would count as progress

• A reduction proving NP-hardness of the planar Euclidean maximum TSP. Gadgets can be checked by computing optimal tours of small instances exactly.
• A polynomial-time algorithm on the real RAM, with a proof, perhaps first for structured inputs such as points in convex position or on few lines.
• Exact optimal tours for benchmark families, which give evidence about the structure of longest tours.

References

1. A. Barvinok, S. P. Fekete, D. S. Johnson, A. Tamir, G. J. Woeginger and R. Woodroofe, The geometric maximum traveling salesman problem, J. ACM 50 (2003), 641–664. doi:10.1145/876638.876640, arXiv:cs/0204024
2. A. I. Barvinok, Two algorithmic results for the traveling salesman problem, Math. Oper. Res. 21 (1996), 65–84. doi:10.1287/moor.21.1.65
3. A. Barvinok, D. S. Johnson, G. J. Woeginger and R. Woodroofe, The maximum traveling salesman problem under polyhedral norms, Proc. IPCO 1998, LNCS 1412, 195–201. doi:10.1007/3-540-69346-7_15

Source

Imported from The Open Problems Project, Problem 49, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.