Assume a set of points $x_i, i=1..n$ and $S$ - the shortest path that is crossing all the points $x_i$ is given. We need to find the order of points in this path. I assume that even if we use simple nearest neighbour like algorithm (with stopping if testing path length exceeds the $S$), we will have a polynomial time solution. This is some kind of simplified Traveling Salesman Problem.
Actually I am unable to estimate the complexity as I am not sure how to cover the topological structure of set of $n$ points.