[Algorithms] 证明支配集问题是NP完全问题

声明：原题目出自《算法概论》，解答部分为原创

Problem ：

  In an undirected graph G = (V, E), we say D ⊆ V is a dominating set if every v∈V is either in D or adjacent to at least one member of D. In the DOMINATING SET problem, the input is a graph and a budget b, and the aim is to find a dominating set in the graph of size at most b, if one exists. Prove that this problem is NP-complete.

Solution：

相关概念：

  支配集（Dominating set）：对一个无向图G（V，E），称 D ⊆ V 是图G的一个支配集，当且仅当对任意v∈V，要么v∈D，要么v至少与D中的一个顶点相邻。

  顶点覆盖（Vertex Cover）：对一个无向图G（V，E），称 S ⊆ V 是图G的一个顶点覆盖，当且仅当图G的任意一条边至少与S中的一个顶点邻接。

  支配集问题（Dominating-set Problem）：输入一个无向图G和预算b，若G存在支配集D且满足|D|<=b，则输出支配集D，否则输出“不存在满足条件的支配集”。

已知条件：

  顶点覆盖问题（Vertex-cover Problem）是 NP-完全问题。

证明过程：

  由已知：顶点覆盖问题是 NP-完全问题，

  欲证明：支配集问题是 NP-完全问题，

  只需要证明：顶点覆盖问题规约到支配集问题。证明如下：

---------------------------------------------------------------------------------------------

  对给定的无向图G，作如下处理：对于图G的任意一边uv，添加一个点w，使得该边的两个顶点u、v分别与w相邻，得到新的一个无向图G’。

  i)若原无向图G存在一个顶点覆盖S，且S满足|S|<= b，则S也可以作为图G’的一个满足条件的支配集。原因如下：

  假设S不是图G’的支配集，即存在点w∈V(G')，使得w∉S且w不与S中的任意顶点相邻。由于图G连通，则必然存在边（u，w）满足u∉S。显然边（u，w）是在原图上添加的一条辅助边，否则，根据条件“S是G的一个顶点覆盖”得“边（u，w）至少有一个顶点属于S”，与“w∉S且u∉S”矛盾。则w为辅助顶点。

  设w对应的边为（u，v），由S是G的一个覆盖，且（u，v）边的顶点u不属于S，则顶点v必然属于S。w与v相邻，即w与S中的一个顶点（v）相邻，与假设矛盾。则证明假设不成立。

  则得证“若S为无向图G的一个顶点覆盖，且|S|<=b，则S是图G’的支配集”。

  ii)若无向图G’存在一个支配集D，且D满足|D|<=b，则图G存在满足条件的顶点覆盖S。原因如下：

  对于G’的边（u，v）及其辅助点w，

    若w∉D，则D也可以看做原图G的一个顶点覆盖S；

    若w∈D且u、v∉D，则将D中的顶点w替换成顶点u或v，可以得到原图G的一个顶点覆盖S；

    若w∈D且u∈D、v∉D（或u∉D、v∈D），则将D中的顶点w删除，可以得到原图G的一个顶点覆盖S；

    若w∈D且u、v∈D，则将D中的顶点w删除，可以得到原图G的一个顶点覆盖S；

  则得证“若无向图G’存在一个支配集D满足|D|<=b，则图G必然存在顶点覆盖S，且|S|<=|D|<=b”。

  综上所述，任何顶点覆盖问题，都可以规约到支配集问题。

------------------------------------------------------------------------------------------

  由于顶点覆盖问题可以规约到支配集问题（Vertex-set problem -> Dominating-set problem），且顶点覆盖问题是NP完全问题，则支配集问题为NP完全问题