1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What if $G$ has an odd number of vertices? I think this proof only works when $G$ has $kn$ vertices for some integer $n$ $\endgroup$ – user127619 Apr 28 at 0:17
  • $\begingroup$ The proof will work for all graphs if $G$ has $n$ vertices, all negative-weight edges have weight -2, and the target weight is 4. $\endgroup$ – j_random_hacker Apr 28 at 4:28
  • $\begingroup$ I made it with an even number for simplicity, but it's clear that Hamiltonian cycles are hard to detect in this case already. If they were not, and the problem was only hard for an odd number of vertices, then adding one extra node to an instance would be a reduction... $\endgroup$ – Bernardo Subercaseaux Apr 28 at 12:52
0
$\begingroup$

If $k$ is a fixed known value and does not depend on the graph, then I doubt it would be possible to do it efficiently:

Verifying if a graph has a cycle of size $k$ can be done by checking all potential paths of size $k$ and verify if one is indeed a cycle. Since there are at most $\begin{pmatrix}n\\k\end{pmatrix}(k-1)! = O(n^k)$ such path in a graph of order $n$, and the verification is done in $O(k) = O(1)$, such an algorithm would be polynomial in the size of the graph (but obviously not in $k$).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy