9
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\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
    Commented Apr 15, 2015 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
    Commented Apr 15, 2015 at 21:58
  • $\begingroup$ Oh, I see my mistaken interpetation $\endgroup$
    – Joe Bebel
    Commented Apr 15, 2015 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
    Commented Apr 16, 2015 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
    Commented Apr 16, 2015 at 21:55

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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