2
$\begingroup$

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?

Resources

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.

Improve this question
$\endgroup$
5
  • $\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
  • $\begingroup$ What if I relax the condition of triangle inequality - perhaps have a recursive arrangement of small sets of points w/known paths assembled into a greater graph. E.g., let a, b, c ,... each be small subgraphs w/known shortest paths. Then let graph A consist of the assembly a -- b -- c -- d... Is the shortest path in A the sum of the shortest paths in each subgraph? $\endgroup$
    – Russ
    2 days ago
  • $\begingroup$ The purpose of my question is to generate large random test sets to assess TSP approximation algorithms. This, of course, pushes the problem out to evaluating the realism of the structured approach compared to the real world (generated sets struggle to match the hardest cases found in the wild.) $\endgroup$
    – Russ
    2 days ago

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.