顶点覆盖到集合覆盖的归约

顶点覆盖到集合覆盖的归约
对于顶点覆盖问题,可以看做是“覆盖问题”,目标是用尽可能少的顶点“覆盖”图中所有的边。
【集合覆盖问题】
集合覆盖问题可以描述为:
给定 n 个元素的集合U,U 的子集S_1,…,S_m 以及数 k, 问在这些子集中有一组子集,它的并等于整个 U 且至多含有 k 个子集?
如图3为一个集合覆盖问题的实例。
在这里插入图片描述
图3 集合覆盖问题实例
在图3中,有3个子集(即数k为3){S_3,S_4,S_5},它的并等于整个 U。
【顶点覆盖\leq_p集合覆盖】
顶点覆盖问题可以归约到集合覆盖问题。
即:如果有一个解集合覆盖的黑盒子,通过输入顶点覆盖的一个实例,调用这个黑盒子,能够解决顶点覆盖问题。
可以使用这样的构造方法:对于每一个顶点i \in V,设集合S_i \subseteq UG 中所有与顶点 i 相连的边。则根据此方法,对每一个顶点构建集合。
U 能够被 S_1,S_2,S_3,…,S_n 中至多 k 个集合覆盖当且仅当 G 有大小至多为 k 的顶点覆盖。
因为如果 S_{i_1},S_{i_2},S_{i_3},…,S_{i_l}l \leq k 个覆盖 U 的集合,那么 G 中的每一条边都可以关联到顶点 i_1,i_2,i_3,…,i_l 中的一个,所以 {i_1,i_2,i_3,…,i_l} 是 G 中大小为 l \leq k 的顶点覆盖。
因此,给定顶点覆盖的实例,利用上述构造方法构造集合覆盖的实例,并且将它输入黑盒子,回答yes当且仅当黑盒子回答yes。

0

Leave a Reply

Your email address will not be published.