Instância: Um gráfico não direcionado com dois vértices distintos s ≠ t e um número inteiro k ≥ 2 .
Pergunta: Existe um caminho em G , de modo que o caminho toque no máximo k vértices? (Um vértice é tocado pelo caminho se o vértice estiver no caminho ou tiver um vizinho no caminho.)
cc.complexity-theory
graph-theory
graph-algorithms
Andras Farago
fonte
fonte
Respostas:
Este problema foi estudado em:
Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg: Problemas de conectividade isolados. SEC 2013: 301-312.
http://arxiv.org/pdf/1212.6176v1.pdf
Eles chamaram isso de problema de caminho isolado. É realmente NP-difícil, e a versão de otimização não tem aproximação de fator constante.
A motivação que os autores fornecem é uma configuração em que as informações são enviadas pelo caminho, e somente os vizinhos e os nós no caminho podem vê-las. O objetivo é minimizar a exposição.
fonte
Editar: Consulte a resposta do usuário20655 abaixo para obter uma referência a um artigo que já comprove a dureza desse problema. Deixarei minha postagem original, caso alguém queira ver essa prova alternativa.
===============
fonte