Seja um gráfico. Um conjunto vértice X ⊆ V é chamado crítico se X ≠ ∅ e nenhum vértice em V ∖ X é adjacente a exatamente um vértice em X . O problema é encontrar um conjunto vértice S ⊆ V de tamanho mínimo de tal modo que S ∩ X ≠ ∅ para cada conjunto crítico X .
O problema tem a seguinte interpretação de espalhar o boato : O vértice espalha o boato ao seu vizinho j se e somente se todos os outros vizinhos de i já estiverem informados. A questão é, então, quantos vértices tenho que informar inicialmente para garantir que todos sejam informados no final.
cc.complexity-theory
graph-theory
co.combinatorics
optimization
Thomas Kalinowski
fonte
fonte
Respostas:
O problema é conhecido como problema de propagação . Aazami provou em sua tese de doutorado que a versão ponderada é NP-completa, mesmo quando o gráfico é plano e os pesos dos nós estão em . A complexidade da versão não ponderada parece ser um problema em aberto.{0,1}
fonte