“判断一个图是否包含一个99大小的顶点覆盖是np完全的”是对的吗？？？
和
“确定图是否包含大小为99的顶点覆盖需要线性时间”，这是对的吗？??
再说一个，如果顶点覆盖问题不允许多项式时间算法，就不可能在多项式时间内解决np完全问题。？？
最佳答案
“确定一个图是否包含大小为99的顶点覆盖是np完全的吗？”
学究：不。
这个问题可以在多项式时间内解决。然而，下面的算法在实际中是完全无用的。
一个n个顶点的图的方法是测试所有c（n，99）可能的顶点覆盖选择。对于每个选择，我们测试所有边（图中最多n*（n-1）个边）以查看是否包含它们的任一顶点。
选择顶点覆盖的方式比n^99要少，所以总体上该算法具有多项式复杂度n^101。
正如j_random_hacker所指出的，这个答案假设99的顶点大小是一个已知的常数。如果99是一个变量，并且是输入的一部分，那么问题就变成了标准的NP-completevertex cover problem。
关于algorithm - NP-完全确定顶点覆盖，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40971824/