algorithm - Verification algorithm for minimum vertex cover?

Question

We know that the minimum vertex cover is NP complete, which means that it is in the set of problems that can be verified in polynomial time.

As I understand it, the verification process would require the following:

1. Verify that the solution is a vertex cover at all
2. Verify that the solution is the smallest possible subset of the source graph that satisfies condition #1

I'm finding it hard to establish that step #2 can be done in polynomial time. Can anyone explain how it is?

Answer 1

最小顶点覆盖是 NP 难的。只有当它被重新表述为一个可以在多项式时间内验证的决策问题时，它才是 NP 完全的。

最小顶点覆盖问题是在给定图中找到最小顶点覆盖的优化问题。

• 实例：图G
• 输出：最小的数k使得G有一个大小为k的顶点覆盖。

如果将问题描述为决策问题，则称为顶点覆盖问题：

• 实例：图G和正整数k。
• 问题：G是否有一个大小为k的顶点覆盖？

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

例如，对于旅行商问题，验证提出的解决方案是否所有城市之间的最短路径是 NP 难的。但是，如果问题被重申为只需要为某个k找到一个小于k总距离的解，那么验证一个解就很容易了。您只需找到建议解决方案的长度并检查它是否小于k。

决策问题公式可以很容易地用于解决一般公式。要找到最短路径，您所要做的就是降低k的值，直到找不到解决方案。