I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):

INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$.

QUESTION: Does $S$ contains a hitting set for $C$ of size $K$ or less, that is, a subset $S' \subseteq S$ with $|S'| \leq k$ and such that $S'$ contains at least one element from each subset in $C$?

The problem definitions from other sources (none of which elaborates on the size of $C$ in relation to $|S|$):






Given a set $S$ with $|S| = n$, a collection $C$ of its subsets can have up to $2^n$ elements (where each element is a subset of $S$).

Given a certificate, $S' \subseteq S$, of the Hitting Set Problem, how could we possibly check if $S'$ contains at least one element from each subset in $C$ in polynomial time w.r.t $n$?


1 Answer 1


You cannot check, in general, whether $S'$ contains at least one element from each subset $C$ in polynomial time w.r.t. $n$.

However, in order to show that the problem is NP it suffices to show that you can check to above condition in polynomial time w.r.t. the instance size, which is in $\Omega( \sum_{X \in C} |X| + \log n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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