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:
- The total length of the cycle is less than D
- The number of nodes included in the cycle is maximal
- 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.