证明加权反馈顶点集是NP完全的

Question

我需要证明加权反馈顶点集（WFVS）是NP完全的。我怎么做，我感到困惑。我不知道该怎么做。

谢谢！ :)

Answer 1

有三个基本步骤来表明问题出现在NP中

1. 决策问题：您能否将问题转化为决策问题？在WFVS问题的情况下，决策问题可能是“给定图G和实数K，是否有一组顶点V使得V满足WFVS的条件？
2. 证书：您能否确定您的决定问题的答案？同样，在WFVS问题的情况下，答案可能是图中的顶点集
3. 验证：您可以在多项式时间内验证证书吗？通过验证多项式时间，您知道问题不是NP-Hard。一些验证步骤可能是：图中的所有顶点/边是？是加权边的总和<= K？等等

这就是你如何知道你的问题在NP中。

NP完成

要表明问题是NP-Complete，您必须找到一个众所周知的NP-Complete问题，例如顶点覆盖或旅行商问题，并通过将已知问题转换为您的问题来证明您的问题与该问题一样困难问题，然后证明你的问题的'是'证书暗示对另一个问题的'是'证书，反之亦然。

这就是你如何表明你的问题是NP完整的。