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完整的）。