# Complexity of weighted cycle in a hamiltonian graph

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!

## 1 Answer

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.

• 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... Dec 12, 2010 at 17:22
• Of course, you're right. I meant $\infty$ instead of 0 -- I corrected my post. Dec 12, 2010 at 17:26
• $n$ works just as well as $\infty$ here. Dec 12, 2010 at 17:54