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

Question

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?

Answer 1

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.