# Hamiltonian cycle on a subset of 2D points, constrained by maximum total length

We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a subset of nodes which satisfies all of the following properties:

1. The total length of the cycle is less than D
2. The number of nodes included in the cycle is maximal
3. If there are more solutions satisfying 1. and 2., choose the one having the smallest cycle length

Note that weights of edges satisfy triangle inequality.

I know how to solve a standard shortest Hamiltonian cycle problem. However, I don't know how to choose a subset of points to start with. The naive solution would involve enumerating all subsets of points (NP) and attempting to construct a Hamiltonian cycle on every such subsets (NP again).

It seems totally intractable, even for a small number of nodes (I expect ~15 nodes). The only heuristic I can think of is constructing a minimum spanning tree for every subset, using the length of a MST as a lower-bound estimate and skipping subsets that obviously break constraint #1.

I hope a better solution exists, ideally without enumerating all subsets of nodes.

## 2 Answers

This problem is known as the (Undirected) Orienteering problem (I'm unaware of any work that examined distances that come from 2D Euclidean embedding).

It is NP-hard (and moreover, $APX$-hard) and there exists a $2+\epsilon$ approximation for it.

• Thank you for naming the problem. I couldn't find it anywhere. Commented Oct 2, 2014 at 9:14
• The journal version of the above mentioned $(2+\epsilon)$-approximation is available at the link below. It has additional results. web.engr.illinois.edu/~chekuri/papers/orienteering-journal.pdf Commented Dec 27, 2014 at 4:22

As RB mentioned, this is the Orienteering problem. For points on a plane, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.5979 gives a PTAS.