Gov*_*mar 4 algorithm graph np-complete vertex
我们知道最小顶点覆盖是NP完全,这意味着它处于可以在多项式时间内验证的一组问题中.
据我了解,验证过程需要以下内容:
我发现很难确定步骤#2可以在多项式时间内完成.谁能解释一下它是怎么回事？
最小顶点覆盖是NP-hard.如果它被重新表述为可以在多项式时间内验证的决策问题,那么它只是NP完全的.
最小顶点覆盖问题是在给定图中找到最小顶点覆盖的优化问题.
- 实例:图G
- 输出:最小数k,使得G具有大小为k的顶点覆盖.
如果问题被陈述为决策问题,则称为顶点覆盖问题:
- 实例:图G和正整数k.
- 问题:G的顶点覆盖大小最多为k吗？
将问题重述为决策问题是使问题NP完全的常见方法.基本上你将"找到最小解k " 形式的开放式问题转变为是/否问题,"对于给定的k,是否存在解决方案？"
例如,对于旅行商问题,验证所提出的解决方案是所有城市之间的最短路径是NP难的.但是,如果问题是重新表述为仅具有找到解决短于ķ总距离对于一些ķ,然后验证的溶液是容易的.您只需找到建议解决方案的长度并检查它是否小于k.
决策问题公式可以很容易地用于解决一般公式.要找到最短的路径,您需要做的就是减去k的值,直到找不到解.