Prove that Hitting Set is NP-Complete

Question

The Hitting Set Problem (HS) is defined as follow. Let $(C,k$)

• $C = \{ S_1, S_2, ..., S_m \}$ collection of subset of S i.e. $ S_i \subseteq S , \forall i$
• $k \in \mathbb{N}$

We want to know if exists ${S}' \subset S$ where $|{S}'| < k$ such that $S_i \cap S' \neq \emptyset $, $i = 1,2,...,m.$

Prove that HS is Np-Complete.

Hint: When $|S_i| = 2$, HS becomes Vertex Cover, already know to be NP-complete.

Answer 1

3SAT is reduced to the Hitting Set problem. Given a 3SAT $\phi$ having $m$ clauses and $n$ variables, define

$$S = \{ x_1, \dots x_n, \overline{x_1}, \dots , \overline{x_n}\}$$ $$S_i=\{y_1, y_2, y_3\}, \text{ if } y_1,y_2,y_3 \in S \text { and } (y_1 \lor y_2 \lor y_3) \text{ is a clause.} $$ $$S_x=\{x, \overline{x}\}, \text{ for all variable } x.$$ $$k=n$$

Assume $\phi$ is satisfiable, then there a is true-value assignment for $n$ variables. So, add $x$ to $S'$ if $x=true$, otherwise add $\overline{x}$ to $S'$.

Now, assume the HS problem has a solution $S'$. Then since for every variable $x$, $S' \cap S_x \neq \emptyset$, $S'$ has at least $n$ literals of the form $x$ or $\overline{x}$ for each variable $x$. Furthermore, no $x$ and $\overline{x}$ may belong to $S'$ at the same time since the size of $S'$ is at most $n$. Also, for each clause $C_i$, $S' \cap S_i \neq \emptyset$ and so for each clause we select $y_i\in S' \cap S_i$, and set $x=true$ if $y_i=x$ and $x=false$ if $y_i=\overline{x}$.

Answer 2

It is easy to show that Hitting Set is in NP. A solution just needs to exhibit the set H – one can easily verify in polynomial time whether H is of size k and intersects each of the sets B1, . . . , Bm.

We reduce from vertex cover. Consider an instance of the vertex cover problem – graph G = (V, E) and a positive integer k. We map it to an instance of the hitting set problem as follows. The set A is the set of vertices V . For every edge e ∈ E, we have a set Se consisting of the two end-points of e. It is easy to see that a set of vertices S is a vertex cover of G iff the corresponding elements form a hitting set in the hitting set instance.

Answer 3

The Hitting Set Problem is equivalent to the Set Cover Problem, that is defined as follow:

INPUT: a collection C of subsets of a finite set S.

SOLUTION: A set cover for S, i.e., a subset $C'\subseteq C$ such that every element in S belongs to at least one member of $C'$.

Given $k$ does it exist a set cover $C'$ such that $\vert C'\vert \leq k$?

This looks like a homework, so I let you figure how, given an instance of Set Cover you can convert it to an equivalent instance of Hitting Set.

Otherwise, if you want to follow the hint, you first show that Hitting Set in in $NP$, that is given a solution you can verify it in polynomial-time.

Then, you show that given a graph $G=(V,E)$, finding a vertex cover of size $k$ is equivalent to find a hitting set of size $k$. That is, if $|E|=m$, you can build a hitting set instance with the same amount of sets.