对于连通无向图，G = (V, E)
和所需的顶点集D，D is a subset of V（即D \in V）
是否NP-hard要找到一个minimum dominating set包含所需顶点集的D?
问问题
423 次
1 回答
1
是的，这是一个NP-hard问题。请参阅以下文档以阅读减量。随意询问您在理解证明方面是否有问题。
http://www.cs.iastate.edu/~chaudhur/cs611/Sp07/notes/lec22.pdf
为了更多地解释你的问题，即添加限制D是V......这样想的一个子集 - 当你试图证明你的问题是NP时，你将已知NP问题简化为问题的特定实例。您的问题的具体实例可能是D=V......并且您可以证明您的问题也是NP. 希望这可以帮助。
于 2013-05-12T17:48:15.740 回答