<p>I don't know about knapsack problem, but it isn't too hard to reduce from Hamiltonian Cycle to this problem (assuming you mean a simple cycle). We start with an arbitrary graph $G$ with $n$ nodes for which we want to find a Hamiltonian cycle. Then we construct $G&#39;$, which is $G$ with the addition of a single node $v$, a single edge from $v$ to an arbitrary node in $G$ with arbitrary weight, and every other edge has weight 1. We then ask if there is a cycle with weight $n$ in $G&#39;$.</p>

<p>If we have a Hamiltonian cycle in $G$, this corresponds to a cycle in $G&#39;$ with weight $n$. This is not a Hamiltonian cycle in $G&#39;$, since it doesn't go through our added vertex $v$. If we have a (simple) cycle with weight $n$ in $G&#39;$, then it must include exactly n nodes. It can't include $v$ since it has degree 1, and can't be part of a cycle. Therefore, this goes through all the nodes in $G$, and thus is a Hamiltonian Cycle in $G$.</p>

<p>Therefore this problem is $\mathcal{NP}$-Complete, unless I misinterpreted your question.</p>

CC BY-SA 2.5
2010-12-11T06:40:43.867Z
2010-12-11T16:34:16.650Z
2010-12-11T16:34:16.650Z
Gautam Kamath
<p>Assume a weighted graph G and a positive value k are given, and you are looking for the complexity of finding a cycle with total weight k; beside you know that no Hamiltonian cycle in G has total weight k. (G is an arbitrary weighted graph, beside you know no hamiltonian cycle would satisfy the total weight k)</p>

<p>1-can someone use reduction from knapsack to conclude that the complexity of finding a cycle with total weight k In G is NP-com? (I guess no!)<br>
2-Is there any idea about the complexity of finding a cycle in G with total weight k when you know no Hamiltonian cycle in G convinces total weight k?</p>

CC BY-SA 2.5
2010-12-11T08:25:34.980Z
This looks homeworky.
Jeffε
CC BY-SA 2.5
2010-12-11T11:25:13.440Z
This is not a homework :((
marjoonjan
CC BY-SA 2.5
2010-12-11T16:45:29.857Z
definitely smells homeworky to me.
Suresh Venkat
<cc.complexity-theory><graph-theory><complexity-classes>
complexity of finding a cycle with total weight k in a graph when you know no hamiltonian cycle in graph satisfies the given weight k
marjoonjan
# complexity of finding a cycle with total weight k in a graph when you know no hamiltonian cycle in graph satisfies the given weight k

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

Assume a weighted graph G and a positive value k are given, and you are looking for the complexity of finding a cycle with total weight k; beside you know that no Hamiltonian cycle in G has total weight k. (G is an arbitrary weighted graph, beside you know no hamiltonian cycle would satisfy the total weight k)

1-can someone use reduction from knapsack to conclude that the complexity of finding a cycle with total weight k In G is NP-com? (I guess no!)  
2-Is there any idea about the complexity of finding a cycle in G with total weight k when you know no Hamiltonian cycle in G convinces total weight k?

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

> **Comments:**
> **username_1**: This looks homeworky.  
> **username_0**: This is not a homework :((  
> **username_2**: definitely smells homeworky to me.  

---

## 1 answers

### Answer by username_3 on 2010-12-11. Score: 4 | Accepted answer

I don't know about knapsack problem, but it isn't too hard to reduce from Hamiltonian Cycle to this problem (assuming you mean a simple cycle). We start with an arbitrary graph $G$ with $n$ nodes for which we want to find a Hamiltonian cycle. Then we construct $G'$, which is $G$ with the addition of a single node $v$, a single edge from $v$ to an arbitrary node in $G$ with arbitrary weight, and every other edge has weight 1. We then ask if there is a cycle with weight $n$ in $G'$.

If we have a Hamiltonian cycle in $G$, this corresponds to a cycle in $G'$ with weight $n$. This is not a Hamiltonian cycle in $G'$, since it doesn't go through our added vertex $v$. If we have a (simple) cycle with weight $n$ in $G'$, then it must include exactly n nodes. It can't include $v$ since it has degree 1, and can't be part of a cycle. Therefore, this goes through all the nodes in $G$, and thus is a Hamiltonian Cycle in $G$.

Therefore this problem is $\mathcal{NP}$-Complete, unless I misinterpreted your question.


---

