HelloKenLee

Hitting Set问题NP-Complete 证明

Posted on By KenLee

问题定义

Hitting Set(碰撞集)问题

定义为: 给出若干集合{$S_1,S_2…S_n$}和一个预算$b$, 我们希望构造一个新的集合$H$,使得$H$集合的元素个数小于等于$b$,而且$H$和所有$S_i$有交集且交集非空。

我们希望证明这个问题为NP-完全问题。

Vertex Cover(顶点覆盖)问题

给出一个无向图$G$,以及一个值$b$。 要求选择一个顶点的集合$S$,$S$包含的元素个数小于$b$, 且$S$中的顶点能够覆盖图$G$的所有边。换句话说,要求$G$中的所有边连接的两个顶点至少有一个在集合$S$中。

该问题在书(《算法概论》)上已经被证明为NP完全问题。

证明

要证明碰撞集问题为NP完全问题,我们得分别证明该问题是NP的,而且该问题是NP难的。

1. NP性证明

给出一个集合$H$,我们很容易在多项式时间内证明其是否一个碰撞集。我们只需要遍历整个$H$,看其元素个数是否小于$b$。接着我们遍历给出的集合们{$S_1…S_n$},分别和$H$求交,看是否为空即可。如果$S_i$集合的大小上限为$m$,时间复杂度为$O(bmn)$, 通过哈希表记录$H$可以把时间复杂度优化成$O(mn)$。

2. NP难证明

要证明碰撞集问题是NP难的,我们选择把一个已知的NP难的问题规约为该问题。我们选择的是顶点覆盖问题。

对于一个碰撞集问题,我们构造一个图$G,~st.$每一个顶点为集合{$S_1…S_n$}中的元素。当2个顶点同属{$S_1…S_n$}的任意一个集合的时候,我们为这两个元素添加一条无向边。(如果两个元素同属多个集合不增加额外的边,因此是一个非膨胀图。)

例子,对于集合们:

构造无向图$G$如下:

我们从图$G$中找小于预算$b$的顶点覆盖$H$。假设存在这样一个顶点覆盖,那么该图$G$的所有边都会被覆盖到,由构造过程知,每一条边的两个顶点都属于{$S_1…S_n$}中的一个集合,因此{$S_1…S_n$}中的每一个集合必定会至少有一个顶点在$H$中,因此顶点覆盖$H$即为所求碰撞集。

比如上述例子中,我们在图$G$中求得其中一个最小顶点覆盖为$H={b,c,e,f}$,不难验证$H$即所求的一个碰撞集: $H \cap S_1 = {b,c}, ~~H \cap S_2 = {b,c}, H \cap S_3 = {e,f}$。

不难知道我们构造图$G$的时间复杂度是多项式的,我们只需要遍历所有集合构造即可。时间复杂度为$O(nm^2)$, $m为S_i$集合的大小上限。

因此假设我们有一个算法能在多项式时间内找到顶点覆盖问题的解,我们就能在这个时间加$O(nm^2)$的时间内找到碰撞集的解。然而顶点覆盖是NP难的,因此碰撞集问题也是NP难的。

结论

综合上述1,2两点,碰撞集问题是NP完全问题。