Isso é difícil de NP? Eu não posso provar isso.

11

Eu tenho um problema e acho difícil de NP, mas não posso provar.

Aqui está um gráfico de camadas, em que a camada 0 é a camada mais alta e a camada L, a mais baixa.

há alguma aresta direcionada entre as camadas, onde uma aresta (A, B) indica que o nó A pode [cobrir] o nó B. E quando A pode cobrir B, todo nó em qualquer caminho de A a B pode cobrir B, B pode cobrir em si.

Finalmente, aqui vem um conjunto de nós S. Preciso escolher outro conjunto de nós ANS e garantir que, para cada nó q em S, exista um nó p no ANS ep cobre q.

Para cada nó existe um custo, e eu preciso tornar o custo total do conjunto ANS mínimo.

Este é um problema difícil de NP? Acho que sim, mas não posso provar.

Você poderia me ajudar?

Muito obrigado.

graphs np qin.sun
fonte
O custo do nó da camada superior é mais caro em qualquer caminho no gráfico.
Sim, de fato parece NP difícil. Observe o problema semelhante de tampa mínima do conjunto. en.wikipedia.org/wiki/Set_cover_problem
Existe alguma restrição na aresta direcionada, como as arestas apenas conecta um nó na camada superior a um nó na camada inferior? Posso esclarecer que não pode haver arestas entre os nós na mesma camada?
Just just
@justhalf Não, não há arestas entre os nós na mesma camada. Obrigado :)
qin.sun

Respostas:

6

Sim, este problema é definitivamente NP difícil. Estou postando esta resposta, pois você precisa de provas.

Se você seguir este link http://en.wikipedia.org/wiki/Set_cover_problem , ele indicará que a versão de otimização do problema de cobertura mínima do conjunto é NP-Hard.

O problema no link:

Dado um conjunto de elementos {1,2, ..., m} (chamado universo) e um conjunto S de n conjuntos cuja união é igual ao universo, o problema da cobertura do conjunto é identificar o menor subconjunto de S cuja união é igual a universo. Por exemplo, considere o universo U = {1, 2, 3, 4, 5} e o conjunto de conjuntos S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Claramente, a união de S é U. No entanto, podemos cobrir todos os elementos com o seguinte número menor de conjuntos: {{1, 2, 3}, {4, 5}}

Você pode relacionar isso ao seu problema da seguinte maneira:

S é o conjunto de nós que cobrem pelo menos um nó no seu conjunto de entrada. Isso pode ser encontrado através da realização de um DFS nos nós de entrada definidos com a direção das bordas invertida.

Agora, o problema descrito no link é um caso especial do seu problema, em que o custo de cada nó é igual e você deseja apenas minimizar o número de nós (conjuntos).

Portanto, seu problema é ainda mais difícil de resolver no caso geral e, portanto, é NP Hard.

Abhishek Bansal
fonte
Eu acho que isso é verdade com a definição do OP, mas ele também nunca especifica se você pode "cobrir" um nó com uma borda na mesma camada que esse nó. Se for esse o caso, o problema parece um pouco diferente. Caso contrário, se você puder cobrir apenas um nó através de uma borda de uma camada superior, ele realmente parecerá equivalente à otimização da cobertura de conjunto
roliu
@roliu Como é que importa se os mesmos nós da camada podem ser cobertos ou não? O problema que eu entendo é que temos um grafo orientado com um percurso entre o nó A para o meio B que A abrange B.
Hum, não tenho certeza, eu acho. É estranho, porque eu não acho que quase todas as informações no OP sejam realmente úteis. As camadas parecem irrelevantes e a transitividade também. Na maioria das vezes, estou esperando o OP esclarecer que ele realmente quis dizer algo diferente. Em particular, você pode mostrar que não é apenas pelo menos tão duro quanto a cobertura do conjunto, é realmente equivalente. Como qualquer cobertura mínima no problema do OP conterá apenas nós vizinhos do seu conjunto de entradas S. Talvez haja custos negativos ou algo parecido ... #
roliu