# 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](https://doi.org/10.1145/876638.876640), [arXiv:cs/0204024](https://arxiv.org/abs/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](https://doi.org/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](https://doi.org/10.1007/3-540-69346-7_15)

## Source

Imported from [The Open Problems Project, Problem 49](https://topp.openproblem.net/p49), 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.