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$
  • 4
    $\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
8
$\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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ can you show a positive and a negative instance? $\endgroup$ – Nick Nov 3 '17 at 2:37
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to ComputerScience@SE. Interesting use of special symbol - it is common to use MathJax, allowing, e.g., proper subscripting: $B_1, \dots, B_m$. $\endgroup$ – greybeard Feb 22 at 23:31
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.

| cite | improve this answer | |
$\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.