Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top