# What is known about the complexity of this covering problem?

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

• Is the sub-problem "$G=(V,E)$ has a critical set $X\neq V$" in $\mathsf{P}$? – Dominic van der Zypen Apr 22 '15 at 13:41
• @DominicvanderZypen Yes. I can start the algorithm in the original post with a singleton $S=\{v\}$. If I get stuck then the complement of the final set is a critical set $\neq V$. Now let's do this for every start vertex $v\in V$. If we reach $S=V$ in each case it follows that every vertex is contained in every critical set, and therefore $V$ is the only critical set. – Thomas Kalinowski Apr 22 '15 at 21:10
• No vertex in $V\X$ is adjacent to exactly one vertex in $X$. Does that mean the vertices in $V\X$ can be adjacent to more than one vertices in $X$? – Rupei Xu May 11 '15 at 9:04