The Hitting Set Problem is defined as having a universal set $ \mathfrak{U}$ , and nonempty sets $ S_i \subseteq \mathfrak{U}$ for $ 1 \leq i \leq n$ , and finding a set $ \mathcal{H} \subset \mathfrak{U}$ such that $ |\mathcal{H} \cap S_i| \geq 1$ for all $ 1 \leq i \leq n$ .

We may ask for the minimal cardinality of $ \mathcal{H}$ , that is, what is the least number of elements needed to “Hit” every $ S_i$ ?

Further, we may use a greedy algorithm to ensure we find a hitting set. In this greedy algorithm, we set $ \mathcal{H} = \emptyset$ , and while we still have sets $ S_i$ that have not been hit, we add to $ \mathcal{H}$ an element whom appears in the most $ S_i$ that have not been hit.

My question is: What is an example of a Universe set $ \mathfrak{U}$ and subsets $ S_i$ , where $ 1 \leq i \leq n$ for some $ n \in \mathbb{N}$ , such that the greedy algorithm above does not find a minimal Hitting Set $ \mathcal{H} \subset \mathfrak{U}$ ?

For a longer (and probably clearer) description, and more info on the Hitting Set problem, see http://theory.stanford.edu/~virgi/cs267/lecture5.pdf, or Prove that Hitting Set is NP-Complete.