3
$\begingroup$

It is well known, that determining the shortest and, the longest Hamilton Cycle of a complete graph with real edge weights are algorithmically two sides of the same medal: one transforms to the other via a sign change of edge weights, requiring at most $O(n)$ additional operations.

I am now wondering, whether the $k$-th-longest Hamilton Cycle problem is $NP$ hard for all $k\in[1,\#T]$ and, if so, what the differences in algorithmic complexity are ($\#T$ denotes the number of tours).
I suspect, that determing the $\frac{\#T}{2}$-th longest Hamilton Cycle is the hardest one and, that it can't be found without the "detour" over either the shortest or the longest one.

Questions: - Which $k$-th longest HC problems are the hardest, resp. the easiest ones?

  • What are the exact time complexities?

  • Are there algorithms that directly determine the $k$-th longest HC, i.e. without determining a $h$-th longest HC?

  • Can the $k$-th longest HC determined from the shortest or longest one in polynomial time?

Improve this question
$\endgroup$
5
  • $\begingroup$ A naive question: Isn't there just (at most) one length of a Hamiltonian cycle of a (fixed) graph; that length being the number of vertices? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 3, 2015 at 4:03
  • 1
    $\begingroup$ Not if edge weights are involved. $\endgroup$
    – The Masked Avenger
    Commented Feb 3, 2015 at 4:13
  • $\begingroup$ Speaking of $k$-longest Hamiltonian Cycles should imply that their existence is assumed and that edge weights are involved. The TSP is for example the task of finding the/a shortest Hamiltonian Cycle. But I will edit my question accordingly. $\endgroup$
    – Manfred Weis
    Commented Feb 3, 2015 at 4:57
  • $\begingroup$ I guess a choice of $ k $ is really a function of $ n $ and #$ T $, and you are assuming that function is polynomial time computable? $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Feb 3, 2015 at 8:06
  • $\begingroup$ I suspect, that given the shortest Hamiltonian Cycle, it is possible to calculate the $k$-longest one in polynomial time for fixed values of $k$, but not for $k(n)$. But I really don't have any clue, how to tackle the problem. $\endgroup$
    – Manfred Weis
    Commented Feb 3, 2015 at 8:33

0

Reset to default

You must log in to answer this question.