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.
题
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.
- Assume the given problem can be solved in polynomial time.
- Use the given problem to solve a problem that we know is NP-Hard in polynomial time
- This creates a contradiction, so the assumption must be incorrect
- Thus, the given problem mustn't be solvable in polynomial time
So, for a problem like this, would this be a proper approach?
- 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.
- Because we can only find the Hamiltonian cycle in NP time, this problem must also only be solvable in NP time.
解决方案
不隶属于 StackOverflow