Hitting Set Problem with non-minimal Greedy Algorithm

Question

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, breaking ties arbitrarily if there are any.

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.

Answer 1

The greedy algorithm always finds a minimal set (inclusion-wise). However, it does not necessarily find a minimum one.

So what does minimal and minimum mean, you might ask. Minimal set in a family of sets (say the set of all hitting sets), is a set that is not a superset of any other set in the family. That means, a minimal hitting set is a hitting set where if you exclude any element from it becomes a non-hitting set. On the other hand, a minimum hitting set is a hitting set of the smallest size. Even though a minimum hitting set might not be unique, all minimum hitting sets are minimal but minimal hitting sets do not have to be minimum.

An example, where the greedy algorithm does not yield a minimum hitting set is

$$U = \{1, 2, 3, 4, 5\}\\ \mathcal{F} = \{ \{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\} \},$$ where $U$ is the universe and $\mathcal{F}$ is the family of sets to be hit. A minimum solution is hence $\{2, 4\}$. Any solution including $1$ is not minimum, since the set must hit $\{2, 3\}$ and $\{4, 5\}$ using at least one element of each resulting in a solution of size at least 3. However, the greedy algorithm includes $1$ in the first step and hence can not yield a minimum solution.