algorithm - 最小顶点覆盖的验证算法？

Question

我们知道最小顶点覆盖是NP完全的，也就是说它在多项式时间内可以验证的问题集中。

据我了解，验证过程需要以下内容:

1. 验证解决方案完全是顶点覆盖
2. 验证解决方案是满足条件 #1 的源图的最小可能子集

我发现很难确定第 2 步可以在多项式时间内完成。谁能解释一下这是怎么回事？

Answer 1

最小顶点覆盖是 NP-hard。如果它是 restated as a decision problem，它只是 NP-complete可以在多项式时间内验证。

The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph.

• INSTANCE: Graph G
• OUTPUT: Smallest number k such that G has a vertex cover of size k.

If the problem is stated as a decision problem, it is called the vertex cover problem:

• INSTANCE: Graph G and positive integer k.
• QUESTION: Does G have a vertex cover of size at most k?

将问题重述为决策问题是使问题成为 NP 完全问题的常用方法。基本上，您将“找到最小解决方案 k”形式的开放式问题转变为是/否问题，“对于给定的 k，是否存在解决方案？ "

例如，对于 travelling salesman problem ，验证建议的解决方案是所有城市之间的最短路径是 NP-hard。但是，如果将问题重新表述为只需要找到一个总距离小于 k 的解决方案，对于某些 k，那么验证解决方案就很容易了。您只需找到建议解决方案的长度并检查它是否小于 k。

决策问题公式可以很容易地用于求解一般公式。要找到最短路径，您只需逐步降低 k 的值，直到找不到任何解决方案。