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