Hitting Set Problem

An instance of the Hitting Set problem is the following:

We are given a ground set $U$ of $n$ elements, subsets $S_1,\dots ,S_m\in U$ , and an integer $k$. We ask whether there is a set $H\in U$ of cardinality $|H|$ at most $k$, so that $H\cap S_j=\varnothing$, for all $j=1,\dots ,m$, that is, whether there are at most $k$ elements in $U$ that “hit” all the sets $S_1,\dots ,S_m$^[Karlsson et al. - Explainable time series tweaking via irreversible and reversible temporal transformations].

The problem is $NP$-Complete.

---

tags: computation-theory algorithms