3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Sep 3 '17 at 2:46
5
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ can you show a positive and a negative instance? $\endgroup$ – Nick Nov 3 '17 at 2:37
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.