Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called *critical* if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex set $S\subseteq V$ of minimum size such that $S\cap X\neq\emptyset$ for every critical set $X$.

The problem has the following rumour-spreading interpretation: Vertex $i$ informs its neighbour $j$ if and only if all other neighbours of $i$ are already informed. The question is then how many vertices do I have to inform initially to make sure that everybody is informed in the end.

In the rumour-spreading interpretation it is easy to see that the decision problem "Is there a solution with $\lvert S\rvert\leqslant K$?" is in NP. For a given $S$ we can check if it is a solution by the following algorithm:

**While** $\exists v\in S$, $w\in V\setminus S$ such that $N(v)\cap(V\setminus S)=\{w\}$ **do** $S\leftarrow S\cup\{w\}$.

If we reach $S=V$ then the set we started with was a solution, and otherwise the complement of the final set $S$ is a critical set which was not hit by the initial set $S$.

cross-posted from cstheory

**Edit**. I've answered on cstheory.