KBSE42

The Hitting Set Problem is actually NP-complete

Problem Description:
Given a set {S1, S2, S3,…, Sn} and budget b, find a set H, where H intersects all Si and the size of H does not exceed b. Prove that the problem is NP-complete

(1) Prove that the problem is an NP problem.
Assuming that all elements of the set H are given, it is obviously possible to verify whether the set H meets the requirements in polynomial time (compare it with Si one by one and check whether the scale exceeds b), so the problem is an NP problem.


(2) Re-prove that the problem is an NP-hard problem.
It is known that the minimum vertex cover problem of a graph is NP-hard (it has been proved in the introduction to algorithms). As long as a method can be found to reduce the minimum vertex cover problem to the hitting set problem, the hitting set can be proved The problem is NP-hard.


The specification is as follows:
Suppose there is a graph G(V,E), then each edge of the graph corresponds to a set Si, and the two points on the edge are the elements of the set, that is, each set has two elements, such as S1={v1 ,v2}, in this way, we can construct |E| sets. The problem of finding the minimum vertex cover of the graph G can be transformed into finding the hitting set of these |E| sets. The vertex with the minimum vertex cover is the element of H, and the minimum vertex cover is b.
So the hitting set is an NP problem and an NP-hard problem, that is, the hitting set is an NP complete problem.

Leave a Reply

Your email address will not be published. Required fields are marked *