<p>The problem is known as the <em>propagation problem</em>. Aazami has proved in his <a href="http://hdl.handle.net/10012/4147">PhD thesis</a> 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.</p>

CC BY-SA 3.0
2015-07-07T22:56:44.680Z
2015-07-07T22:56:44.680Z
Thomas Kalinowski
<p>Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called <em>critical</em> 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$.</p>

<p>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.</p>

CC BY-SA 3.0
2015-04-15T07:23:42.060Z
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
CC BY-SA 3.0
2015-04-15T21:58:55.900Z
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
CC BY-SA 3.0
2015-04-15T22:20:57.413Z
Oh, I see my mistaken interpetation
Joe Bebel
CC BY-SA 3.0
2015-04-16T19:07:59.893Z
Very interesting question, one minor quibble: you probably want to require your critical sets to be nonempty (otherwise there is no $S$).
Klaus Draeger
CC BY-SA 3.0
2015-04-16T21:25:31.693Z
A question: suppose that $E = \{ (1,3), (2,3), (3,4) \}$ is $X = \{ 1,2\}$ critical ?
Marzio De Biasi
CC BY-SA 3.0
2015-04-16T21:30:26.367Z
@MarzioDeBiasi, didn't he answer that in the first comment? (the answer being ‘yes’) [and, btw, this why I tried to reject the first edit]
Radu GRIGore
CC BY-SA 3.0
2015-04-16T21:42:05.397Z
It is worth noting that the decision version of this problem is in $\Sigma_2^p$, but I don't see directly how it might be in NP
Joe Bebel
CC BY-SA 3.0
2015-04-16T21:55:57.587Z
@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
CC BY-SA 3.0
2015-04-17T13:35:04.833Z
@MarzioDeBiasi, well, 2!=1 and also 0!=1, so none of {3,4} adjacent to exactly 1 vertex. So, {1,2} is critical.
Radu GRIGore
CC BY-SA 3.0
2015-04-17T16:31:53.930Z
@RaduGRIGore: ouch, now I see it :-S
Marzio De Biasi
<cc.complexity-theory><graph-theory><co.combinatorics><optimization>
Is the complexity of this covering problem known?
Thomas Kalinowski
# Is the complexity of this covering problem known?

(Asked by: username_0 on 2015-04-15)

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.

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics, optimization

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: Oh, I see my mistaken interpetation  
> **username_2**: Very interesting question, one minor quibble: you probably want to require your critical sets to be nonempty (otherwise there is no $S$).  
> **username_3**: A question: suppose that $E = \{ (1,3), (2,3), (3,4) \}$ is $X = \{ 1,2\}$ critical ?  
> **username_4**: @MarzioDeBiasi, didn't he answer that in the first comment? (the answer being ‘yes’) [and, btw, this why I tried to reject the first edit]  
> **username_1**: It is worth noting that the decision version of this problem is in $\Sigma_2^p$, but I don't see directly how it might be in NP  
> **username_0**: @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.  
> **username_4**: @MarzioDeBiasi, well, 2!=1 and also 0!=1, so none of {3,4} adjacent to exactly 1 vertex. So, {1,2} is critical.  
> **username_3**: @RaduGRIGore: ouch, now I see it :-S  

---

## 1 answers

### Answer by username_0 on 2015-07-07. Score: 5

The problem is known as the *propagation problem*. Aazami has proved in his [PhD thesis](http://hdl.handle.net/10012/4147) 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.


---

