Czy znana jest złożoność tego problemu?

Niech będzie wykresem. Zestaw wierzchołek nazywa krytyczna jeśli i nie wierzchołek w przylega dokładnie jeden wierzchołek w . Problemem jest znalezienie zbiór wierzchołków z co najmniej taką wielkość, że każdego niezbędny zestaw .$G=(V,E)$$X\subseteq V$$X\neq\emptyset$$V\setminus X$$X$$S\subseteq V$$S\cap X\neq\emptyset$$X$

Problem ma następującą interpretację rozpowszechniającą pogłoski: Vertex przekazuje pogłoskę swojemu sąsiadowi$i$$j$ wtedy i tylko wtedy, gdy wszyscy inni sąsiedzi $i$są już poinformowani. Pytanie brzmi zatem, ile wierzchołków muszę początkowo poinformować, aby upewnić się, że wszyscy zostali poinformowani na końcu.

Problem ten znany jest jako problem propagacji . Aazami udowodnił w swojej rozprawie doktorskiej, że ważona wersja jest NP-kompletna, nawet jeśli wykres jest płaski, a masy węzłów są w$\{0,1\}$. Złożoność wersji nieważonej wydaje się być otwartym problemem.