A complexidade desse problema de cobertura é conhecida?

9

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 .G=(V,E)XVXVXXSVSXX

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.iji

Thomas Kalinowski
fonte
Isso tem uma solução bastante simples, portanto, talvez o problema tenha mais condições do que o especificado; ignorando o caso especial e, se G estiver ligado, a cada vértice v com grau > 1 tem um conjunto crítico V { v } associado com ele, de modo que apenas vizinhos de exclusivamente deg 1 vértices podem ser em S . Se esse vértice existe, G é um gráfico em estrela e seu centro (como um singleton) é o S mínimo único . Se G não estiver conectado, observe cada componente conectado. X=VGv>1V{v}SGSG
21715 Joe
11
Para uma estrela com n 2 folhas, cada conjunto de duas folhas é crítico e, portanto, a solução ideal é obter n - 1 folhas. K1,nn2n1
21415 Thomas Thomas Kalinowski
Oh, eu vejo a minha interpetation equivocada
Joe Bebel
Pergunta muito interessante, uma pequena queixa: você provavelmente deseja exigir que seus conjuntos críticos não sejam vazios (caso contrário, não há ). S
Klaus Draeger
11
@ JoeBebel: O problema de decisão "Existe uma solução definida com tamanho no máximo K ?" está em NP. Você pode verificar se um conjunto S é uma solução pelo seguinte algoritmo. Enquanto não há um vértice v S que tem exatamente na vizinha w fora S , adicione w a S . Se S contiver eventualmente todos os vértices, seu conjunto inicial será uma solução; caso contrário, você ficará paralisado e o complemento do conjunto final será um conjunto crítico; portanto, o S inicial não será uma solução. SKSvSwSwSSS
Thomas Kalinowski

Respostas:

5

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}

Thomas Kalinowski
fonte