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

<p>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.</p>

CC BY-SA 2.5
2010-12-12T17:22:57.190Z
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...
marjoonjan
CC BY-SA 2.5
2010-12-12T17:26:26.450Z
Of course, you're right. I meant $\infty$ instead of 0 -- I corrected my post.
Karolina Sołtys
CC BY-SA 2.5
2010-12-12T17:54:18.850Z
$n$ works just as well as $\infty$ here.
Peter Shor 
CC BY-SA 2.5
2010-12-12T16:56:09.130Z
2010-12-12T17:25:11.833Z
2010-12-12T17:25:11.833Z
Karolina Sołtys
<p>Assume a weighted graph G and a positive value k are given.  </p>

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

<p>pointing to papers and books is also welcome!<br>
I wish it wouldn’t look as a homework!</p>

<cc.complexity-theory><graph-theory>
Complexity of weighted cycle in a hamiltonian graph
marjoonjan
# Complexity of weighted cycle in a hamiltonian graph

(Asked by: username_0 on 2010-12-12)

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!

**Tags:** cc.complexity-theory, graph-theory

---

## 1 answers

### Answer by username_1 on 2010-12-12. Score: 4 | Accepted 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.

> **Comments:**
> **username_0**: 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...  
> **username_1**: Of course, you're right. I meant $\infty$ instead of 0 -- I corrected my post.  
> **username_2**: $n$ works just as well as $\infty$ here.  

---

