cycle - 使用 NP 减少

Question

我在理解使用 NP 问题的减少时遇到了一些困难，希望得到澄清。考虑以下问题：

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.

我知道关于这个主题还有其他主题，但我仍然不确定我是否理解如何进行这样的减少。

据我了解，这就是您处理此类问题的方式。

1. 假设给定的问题可以在多项式时间内解决。
2. 使用给定的问题来解决我们知道在多项式时间内是 NP-Hard 的问题
3. 这就产生了矛盾，所以假设一定是不正确的
4. 因此，给定的问题一定不能在多项式时间内解决

那么，对于这样的问题，这是一个合适的方法吗？

1. 如果我们选择 k 作为图中哈密顿循环的长度（假设有一个），这意味着这个问题可以用来在图中找到哈密顿循环。
2. 因为我们只能在 NP 时间内找到哈密顿循环，所以这个问题也必须只能在 NP 时间内解决。

Answer 1

这看起来很像家庭作业，所以我只会给你一个提示，但请尝试考虑一个V带有k节点的未加权图。什么相当于找到一个长度为的循环k，这可以用您假设的多项式算法来解决？尝试从这个开始。