NP完整吗？

Question

决策问题：对于给定的图G和数字“a”，“b”，需要回答是否存在具有至少'b'大小的累积邻域的一组'a'顶点。我们如何证明这个问题是NPC？

Answer 1

我认为如果你可以用多项式时间解决这个问题，你可以在多项式时间内解决https://en.wikipedia.org/wiki/Maximum_cut。根据文章，Max-Cut中的决策问题是“给定一个图G和一个整数k，确定在G中是否有至少k的大小切割”。

给出的东西，解决您的A/B版本的问题，我会通过设置b = k并尝试a = 1,2,3..size的图解来解决Max-Cut版本，该图形仍然会有成本多项式在输入大小。 （或者可能b = k + a，取决于你所指的邻居大小的细节）。

（所以是的，我认为你的问题是NP完整的）。