0
$\begingroup$

Assume a weighted graph G and a positive value k are given.

What is the complexity of finding a cycle with total weight k when G is Hamiltonian or Hamiltonian-connected?

pointing to papers and books is also welcome!
I wish it wouldn’t look as a homework!

Improve this question
$\endgroup$
4
$\begingroup$

If we are asking for a simple cycle the problem is NP-complete by a reduction from the Hamiltonian cycle problem.

We want to find a Hamiltonian cycle in a graph $G$. We assign weight 1 to all edges of $G$, and add to this graph all the other edges with weight $\infty$. We have thus created a clique, which is obviously Hamiltonian, and we ask whether there exist a cycle with weight $n$ in it.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Good idea, but I think your answer should change a little bit, because in this case someone can just traverse all edges in $O(n^2)$ (in a graph with $n$ vertices) and pick those edges with weight 1! I think it is necessary to build a Hamiltonian cycle with random total weight, and then add other edges with other random weights. Thanks... $\endgroup$
    – marjoonjan
    Dec 12 '10 at 17:22
  • $\begingroup$ Of course, you're right. I meant $\infty$ instead of 0 -- I corrected my post. $\endgroup$
    – Karolina Sołtys
    Dec 12 '10 at 17:26
  • 2
    $\begingroup$ $n$ works just as well as $\infty$ here. $\endgroup$
    – Peter Shor
    Dec 12 '10 at 17:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.