找到一个包含某些期望顶点的最小控制集是NP困难的吗？

Question

对于连通的无向图，G = (V, E)

和期望的顶点集D，D is a subset of V (即D \in V)

查找包含所需顶点集D的minimum dominating set是否为NP-hard

Answer 1

是的，这是一个NP-hard问题。请参阅以下文档以阅读缩减。如果你在理解证据方面有问题，请随时询问。

http://www.cs.iastate.edu/~chaudhur/cs611/Sp07/notes/lec22.pdf

为了更多地解释您的问题，例如，添加限制D是V.....think的子集，如下所示--当您试图证明您的问题是NP时，您将一个已知的NP问题简化为您的问题的特定实例。你的问题的具体实例可以是一个案例，当你可以证明你的问题也是NP时。希望这能有所帮助。