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?

  • 1
    $\begingroup$ This looks homeworky. $\endgroup$
    – Jeffε
    Dec 11 '10 at 8:25
  • $\begingroup$ This is not a homework :(( $\endgroup$
    – marjoonjan
    Dec 11 '10 at 11:25
  • 1
    $\begingroup$ definitely smells homeworky to me. $\endgroup$ Dec 11 '10 at 16:45

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.


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.