# Hitting Set Problem with non-minimal Greedy Algorithm

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.

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