# Is the complexity of this covering problem known?

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$ spreads the rumour to 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.

• This has a pretty simple solution, so perhaps the problem has more conditions than specified; ignoring the special case $X=V$ and if $G$ is connected, every vertex $v$ with degree $>1$ has a critical set $V\setminus\{v\}$ associated with it, so only neighbors of exclusively deg 1 vertices can be in $S$. If such a vertex exists, then $G$ is a star graph and its center (as a singleton) is the unique minimal $S$. If $G$ is not connected then look at each connected component. – Joe Bebel Apr 15 '15 at 7:23
• For a star $K_{1,n}$ with $n\geqslant 2$ leaves, every set of two leaves is critical, and therefore the optimal solution is to take $n-1$ leaves. – Thomas Kalinowski Apr 15 '15 at 21:58
• Oh, I see my mistaken interpetation – Joe Bebel Apr 15 '15 at 22:20
• Very interesting question, one minor quibble: you probably want to require your critical sets to be nonempty (otherwise there is no $S$). – Klaus Draeger Apr 16 '15 at 19:07
• @JoeBebel: The decision problem "Is there a solution set $S$ of size at most $K$?" is in NP. You can check if a set $S$ is a solution by the following algorithm. While there is a vertex $v\in S$ which has exactly on neighbour $w$ outside $S$, add $w$ to $S$. If $S$ contains eventually all vertices then your initial set was a solution, otherwise you get stuck, and the complement of the final set is a critical set, so the initial $S$ was not a solution. – Thomas Kalinowski Apr 16 '15 at 21:55

The problem is known as the propagation problem. Aazami has proved in his PhD thesis that the weighted version is NP-complete even when the graph is planar and the node weights are in $\{0,1\}$. The complexity for the unweighted version seems to be an open problem.