algorithm - NP完全吗？

Question

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

Answer 1

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

给定可以解决您的 a/b 版本问题的方法，我将通过设置 b=k 并尝试 a=1,2,3.. 图形大小来解决 Max-Cut 版本，这仍然会有成本多项式输入大小。 (或者可能 b=k+a 取决于你所说的邻域大小的细节)。

(是的，我认为您的问题是 NP 完全问题)。