# Given a set of sets, find the magnitude (number of elements) of the smallest set containing at least one element from each set

I know that the hitting problem is NP hard, but is it possible to find the magnitude of the smallest set? Also, provide the runtime.

• welcome to CS! What have you tried? – Yamar69 Oct 24 '19 at 7:26

When we say that hitting set is NP-hard, we mean that the following decision problem is NP-hard: given a set system $$S$$ and an integer $$k$$, decide whether there is a hitting set for $$S$$ of size at most $$k$$.