Planar Euclidean Maximum TSP

Definitions and mathematical statement

Given $n\ge3$ distinct points $P=\{p_1,\ldots,p_n\}$ in $\mathbb R^2$, a tour is a cyclic permutation $\sigma$ of all points, with Euclidean length \[ \mathcal L(\sigma)=\sum_{i=1}^{n} \|p_{\sigma(i)}-p_{\sigma(i+1)}\|_2, \qquad\sigma(n+1)=\sigma(1). \] The planar Euclidean maximum traveling-salesperson problem asks for a tour maximizing this sum. What is the computational complexity of this exact optimization problem: does it have a polynomial-time algorithm, or can an appropriate hardness result be established?

The tour may cross itself; imposing simplicity would change the feasible set. All points are visited once before returning to the start, and the objective is total length, not the longest single edge or a bottleneck statistic. The dimension is fixed at two, and distances come from the Euclidean norm.

A complexity statement must specify its numerical model. One may use exact real arithmetic for geometric operations; with rational coordinates in a bit model, comparisons of sums of square roots also need to be accounted for. The question concerns exact optimality. A polynomial-time approximation scheme, or an algorithm for maximum TSP in a different metric or dimension, does not by itself determine this planar exact complexity.

Short English statement

Determine the complexity of finding a maximum-length Euclidean Hamiltonian tour through a planar point set.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500049 (AMR-054-0049), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 49. Original source indexed by AMR-054-0049. https://topp.openproblem.net/p49.
• S3 The Open Problems Project, original numbered problem and status notes. https://topp.openproblem.net/p49.