Search code examples
cyclereductionnp

Using NP Reductions

I have been having some difficulty understanding reductions using NP problems and would like clarification. Consider the following problem:

Show that the following problem is NP-Complete by designing
a polynomial-time reduction algorithm from an already known
NP-Complete problem.

Problem: Given an undirected graph G=(V,E) and integer k,
         test whether G has a cycle of length k.

I know there are other topics regarding this subject, but I am still not sure I understand how reductions like this would be done.

It is my understanding that this is how you would approach a problem such as this.

  1. Assume the given problem can be solved in polynomial time.
  2. Use the given problem to solve a problem that we know is NP-Hard in polynomial time
  3. This creates a contradiction, so the assumption must be incorrect
  4. Thus, the given problem mustn't be solvable in polynomial time

So, for a problem like this, would this be a proper approach?

  1. If we choose k to be the length of the Hamiltonian cycle in the graph (assuming there is one) that means that this problem could be used to find the Hamiltonian cycle in the graph.
  2. Because we can only find the Hamiltonian cycle in NP time, this problem must also only be solvable in NP time.
Solution

  • This looks rather like homework so I'll only give you a hint, but try consider a unweighted graph V, with k nodes. What is equivalent to finding a cycle with length k, which is solvable with the algorithm you assumed that is polynomial? Try to proceed from this.