8.9 In the HITTING SET problem, we are given a family of sets {S1,S2,…,Sn}, and a budget b, and we wish to find a set H of size ≤b which intersects every Si, if such an H exists, In other words, we want H⋂Si≠∅ for all i.
Show that HITTING SET is NP-complete.
碰撞集（Hitting Set）问题是指给定一组集合 {S1,S2,…,Sn}和一个预算b，我们希望找到一个集合H，满足H与所有的Si相交（存在公共元素）且H的大小不超过预算b。即是说，H⋂Si≠∅。
现在要求证明碰撞集问题是一个NP完全问题。
证明如下：
首先需要知道顶点覆盖问题。顶点覆盖（Vertex Cover）问题是指给定图G(V, E)和预算k，希望从V中找到一个大小小于等于k的顶点集合U，使得U能够覆盖所有的边，即V每一条边至少有一个顶点属于U。
顶点覆盖问题是NP完全的，现在通过将顶点覆盖问题规约到碰撞集问题来完成证明。
对于顶点覆盖问题中的G的每一条边e=(u,v)，令Si={u,v}，则得到一组集合{S1,S2,…,S|E|}，每一个集合Si对应G的一条边，集合的元素为对应边的两个顶点。
由于顶点覆盖问题中要求所有的边都被覆盖到，即每一条边至少有一个顶点属于覆盖集U中，这意味着覆盖集U与所有的Si都相交，而击中集问题中H⋂Si≠∅，即U与H是等价的。
同时，覆盖集U最多k个点对应碰撞集H最多有b个元素。
这样，实现了顶点覆盖问题到击中集问题的归约。
因此击中集问题是NP完全问题。
本文为博主原创文章，转载请注明出处。