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.

  • $\begingroup$ 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. $\endgroup$ – Joe Bebel Apr 15 '15 at 7:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Kalinowski Apr 15 '15 at 21:58
  • $\begingroup$ Oh, I see my mistaken interpetation $\endgroup$ – Joe Bebel Apr 15 '15 at 22:20
  • $\begingroup$ Very interesting question, one minor quibble: you probably want to require your critical sets to be nonempty (otherwise there is no $S$). $\endgroup$ – Klaus Draeger Apr 16 '15 at 19:07
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.