Просмотр исходного текста страницы Minimum Hitting Set

Для данного семейства подмножеств найти минимальное число элементов S таких, что для любого подмножества из данного семейства в нем найдется хотя бы один элемент из S (hitting set). Более формально:

<latex>
Дано:
\begin{itemize}
    \item Множество $S={s_1, \ldots, s_n}$,
    \item Набор $С$ из подмножеств $S_1, \dots, S_m$  над $S$.
\end{itemize}

Найти минимальное подмножество $S' \subseteq S$, такое,
что для каждого подмножества $S_j$, в ней есть хотя бы один элемент из него.
</latex>