算法概论Chapter 8 :p20

Answer:
可以将顶点覆盖问题归约到支配集问题。若要在图 ( ) , GVE中求得不大于b 的一个 顶点覆盖，可以先对图G 做一个预处理：对每条边( ) , u v E ∈ ，添加一个辅助顶点w， 及两条边() , uw和( ) , vw，如下图所示：

对每条边都这样处理后得到一个新图 ’ G 。容易看出，若原图G 中存在不大于b 的 顶点覆盖，这个顶点覆盖也是新图 ’ G 的一个支配集。反过来，若新图 ’ G 中存在一 个不大于b 的支配集，那么对这个支配集进行一些处理后也能得到一个图G 的不大 于b 的顶点覆盖。
处理过程如下：设该支配集为D，对于每条边( ) , uv 及相应的辅助顶点w，若 wD ∉ ，则不用做任何处理，若wD ∈ 且 ,u v D ∉ ，那么可以在D中将w替换成u 或v，若wD ∈ 同时uDvD ∈ ∨ ∈，则直接将w从D中删掉即可。