Proving a problem is NP Hard Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted value. It's fixed and known beforehand to everyone. So $k$ is NOT an input to this algorithm.
I want to show the problem is NP hard, so this means I have an oracle that tells me whether or not a graph has a cycle whose sum of edge weights equals $k$ for a fixed, known value of $k$.
I thought about reducing from Hamiltonian cycle. So I want to show that I can use this oracle to solve Hamiltonian cycle problems.
Let $G$ be a graph. I want to see if $G$ has a Hamiltonian cycle. I try to construct a new graph to provide to the oracle but I'm not sure how to do so. I think it needs to have $k$ vertices so I tried doing casework on when $G$ has more or less than this many vertices.
I can show that I can solve Hamiltonian cycle problems with $k$ vertices by constructing a new complete graph where edge weights are $1$ if it was in the original graph and a really large nunber otherwise. Then running the oracle on this graph returns true only if there's a Hamiltonian cycle with $k$ vertices. But this doesn't handle the general case. Is this proof fine?
But I'm stuck. Any help is appreciated.
Let $G$ be a graph with $2n$ vertices, and choose any node $v$. The edges touching $v$ have weight $n$, and all other edges have weight $-1$. Note that any Hamiltonian cycle in $G$ will have two edges touching $v$ (which add up to $2n$) and $2n-2$ edges of weight $-1$, so the total weight of the cycle is exactly $2$.
Therefore, if $G$ has a hamiltonian cycle, it has a cycle of weight exactly $2$.
Moreover, assume $G$ has a cycle of weight exactly $2$. Such a cycle can either include $v$ or not. If it doesn't include $v$, all its edges will be negative, contradicting a total weight of $2$. If it includes $v$, then it must include two edges of weight $n$, and thus the remaining part of the cycle must be a path, using only edges of weight $-1$, and with total weight equal to $-2n+2$. That meeans such a path must contain $2n-2$ edges, and therefore have $2n-1$ nodes. When connecting said path to-and-from $v$, you have a Hamiltonian cycle.
This means that if you could decide in polynomial time whether $G$ has a cycle of weight $2$ (which is a fixed constant), you could decide whether it has a Hamiltonian cycle in polynomial time.