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.

— Thomas Kalinowski
źródło

To dość proste rozwiązanie, więc być może problem ma więcej warunków niż podano; ignorując specjalny przypadek

X = V

$X=V$ i jeśli

G

$G$ jest połączony, każdy wierzchołek

v

$v$ ze stopniem naukowym

> 1

$>1$ ma zestaw krytyczny

V ∖ {v}

$V\setminus\{v\}$ związane z tym, więc mogą przebywać tylko sąsiedzi o wierzchołkach wyłącznie deg 1

S

$S$ . Jeśli taki wierzchołek istnieje, to

G

$G$ jest wykresem gwiazd, a jego środek (jako singleton) jest unikalnym minimum

S

$S$ . Gdyby

G

$G$ nie jest podłączony, następnie spójrz na każdy podłączony komponent.

— Joe Bebel,

Dla gwiazdy

K_{1, n}

$K_{1,n}$ z

n ⩾ 2

$n\geqslant 2$ liście, każdy zestaw dwóch liści jest krytyczny, dlatego też należy podjąć optymalne rozwiązanie

n - 1

$n-1$ pozostawia.

— Thomas Kalinowski

Och, widzę moją błędną interpretację

— Joe Bebel

Bardzo interesujące pytanie, jedna drobna sprzeczka: prawdopodobnie chcesz, aby twoje zestawy krytyczne były niepuste (inaczej nie będzie

S

$S$ ).

— Klaus Draeger

@JoeBebel: Problem decyzyjny „Czy istnieje zestaw rozwiązań

S

$S$ co najwyżej wielkości

K

$K$ ? ”w NP. Możesz sprawdzić, czy zestaw

S

$S$ jest rozwiązaniem według następującego algorytmu. Podczas gdy istnieje wierzchołek

v \in S

$v\in S$ który ma dokładnie na sąsiada

w

$w$ na zewnątrz

S

$S$ , Dodaj

w

$w$ do

S

$S$ . Gdyby

S

$S$ zawiera ostatecznie wszystkie wierzchołki, wtedy początkowy zestaw był rozwiązaniem, w przeciwnym razie utkniesz, a dopełnienie zestawu końcowego jest zestawem krytycznym, więc początkowy

S

$S$ nie było rozwiązaniem.

— Thomas Kalinowski

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.

— Thomas Kalinowski
źródło