I'm interested in testing some Traveling Salesperson (TSP) greedy approximation algorithms for finding the shortest Hamiltonian path for very large graphs. Assume I can construct whatever graph I choose; how could I build a graph with a known shortest Hamiltonian path in polynomial time with edge distances that satisfy the triangle inequality (edited 1/3/2023)?

A trivial way is to create a "straight line" sequence of vertices $v_i$ such that the distance from some vertex $v_i$ to its immediate neighbors $\delta(v_{i-1},v_i) = \delta(v_i,v_{i+1}) = d$ for some constant distance $d$, but that the distance from $v_i$ to all other vertices is greater than $d$. Such a straight line graph is also isomorphic to a "nautilus," wrapping around itself, and other shapes.

The problem is that a greedy algorithm that selects the shortest edge lengths will find the shortest Ham path in this trivial graph in polynomial time. One such algorithm is Krari et al, the Multi-Fragment Tour Construction.

What I want is a deterministic polynomial time way to build a non-trivial graph, one where the shortest Hamiltonian path maybe cannot be found in deterministic polynomial time.

Maybe this construction problem itself is NP complete? Can a deterministic polynomial time algorithm create an optimization problem space that cannot be solved in deterministic polynomial time?


There are a few sites offering data and other information to researchers, indirectly suggesting that this is hard to do, at the least, or maybe not possible.

Triangle Inequality Restriction

As originally asked, a simple algorithm for vertices $v_i, v_{i+1}$ and corresponding edges $e_{i,i+1}$ would be to set edge weight $$e_{i,i+1} \leftarrow 1$$ and $$e_{i,j\neq i+1} \leftarrow 1+\epsilon$$producing the shortest tour as the simple list of vertices $v_0, v_1, v_2, \dots$

However, this violates the triangle inequality which says for weight function $\omega_{i,j}$ as the edge weight/distance between vertices $v_i$ and $v_j$, that $$\omega_{i,j} \leq \omega_{i,k} + \omega_{k,j}$$In plain language, walking directly to the conference takes less time than first walking to the pub and then walking to the conference, unless walking to the conference would take you right past the pub on the way. A counterexample, violating the triangle inequality, is if the walk to the pub were quicker and a bus zipped you from the pub directly to the conference.

  • $\begingroup$ These are sometimes called 'planted solutions'. $\endgroup$
    – D.W.
    Dec 9, 2022 at 19:49
  • 1
    $\begingroup$ I assume that the input for the algorithm is the number of vertices $n$. Since the algorithm is deterministic, then it means that for every $n$ it only constructs a single graph. Is it what you want? $\endgroup$
    – Dmitry
    Dec 9, 2022 at 21:06
  • $\begingroup$ Yes, it should construct a single, non-trivial graph. I'm seeing some other sites that offer test data, indicating that this is at least not easy, and maybe not possible. I'll update my post. $\endgroup$
    – Russ
    Dec 10, 2022 at 13:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy