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.

  • $\begingroup$ this looks harder than a typical NP-complete problem, as you quantify over sets (the critical sets) which are already (most probably) hard to compute... $\endgroup$ – Dima Pasechnik Apr 21 '15 at 11:12
  • $\begingroup$ @DimaPasechnik Note that in order to check feasibility it is not necessary to know all critical sets. The decision version of the problem is in NP, and I've added that to the question. $\endgroup$ – Thomas Kalinowski Apr 21 '15 at 22:19
  • $\begingroup$ Is the sub-problem "$G=(V,E)$ has a critical set $X\neq V$" in $\mathsf{P}$? $\endgroup$ – Dominic van der Zypen Apr 22 '15 at 13:41
  • $\begingroup$ @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. $\endgroup$ – Thomas Kalinowski Apr 22 '15 at 21:10
  • $\begingroup$ 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$? $\endgroup$ – Rupei Xu May 11 '15 at 9:04

Your Answer

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

Browse other questions tagged or ask your own question.