Alguém já viu um problema de gráfico NP como este antes?
-
29-09-2020 - |
Pergunta
Eu tenho um seguinte problema baseado em gráfico:
- Entrada:inteiros positivos K e L, gráfico não direcionado G
- Eu tenho que escolher K vértices deste gráfico
- No caminho entre cada par de K vértices escolhidos deve haver pelo menos L vértices, i.e.deve haver um "espaço entre" cada dois vértices escolhidos feitos de pelo menos L vértices.
É claro que o que foi dito acima pode não ser possível para um determinado caso de problema, então tenho que verificar isso.Tenho certeza que esse problema é NP ou mesmo NP-completo, pois tem a ver com caminhos com restrição de comprimento.Você já encontrou um problema semelhante?Você tem uma ideia de como reduzi-lo a algum problema mais conhecido, possivelmente NP, e.g.cobertura de vértices ou coloração de gráfico?
Além disso, observe que meu gráfico é um gráfico de grade, que pode não ser "completo", mas um subgráfico de uma grade retangular completa.
Solução
Isso é conhecido como a distância- $ D $ Conjunto independente, ou seja, você está procurando um conjunto independente de tamanho $ k $ onde a distância entre todos os dois elementos na solução é pelo menos $ D $ .
O problema é NP-completo mesmo em gráficos planares de acordo com [1], mas não sei sobre sua complexidade em grades parciais.
Em relação às reduções, você provavelmente pode tomar a $ D $ 'th poder do gráfico e encontre um conjunto independente (distância 1) nisso. A reivindicação é que qualquer solução aqui é uma distância- $ D $ Conjunto independente no original, mas você precisa verificar isso.
.
[1] Eto, Hiroshi, Fengrui Guo e Eiji Miyano. "Distância- $ D $ Problemas de conjunto independente para gráficos bipartidos e cordados". Journal of Combinatorial Optimization 27, no. 1 (2014): 88-99.
Outras dicas
No caso especial em que $L=1$, Isto é o problema de conjunto independente máximo, que é NP-difícil em gráficos gerais.Portanto, seu problema também é NP-difícil em gráficos gerais.
Você poderia tentar esperar por um algoritmo que seja específico para a classe de gráficos que você possui (acho que o conjunto independente máximo pode ser calculado eficientemente em gráficos bipartidos, e os gráficos de grade são bipartidos, então você pode tentar generalizar esse algoritmo), ou você pode tentar usar um algoritmo padrão para conjunto/clique independente máximo, ou você pode tentar usar um solucionador SAT.Deve ser fácil formular isso como uma instância MaxSAT:você tem uma cláusula para cada par de vértices que estão dentro da distância $L+1$ (ou menos), e você pede ao solucionador SAT para minimizar o número de variáveis definidas como verdadeiras.
Parece verificando se há uma subgraph de G-VERRES de G isso é locorrável usando as regras do problema de coloração do gráfico.Quero dizer, se todos os vérticos K são coloridos com a mesma cor que satisfazem sua condição.
Como a coloração do gráfico em NP-Completar U pode verificar uma determinada solução no tempo polinomial.
Então, talvez, talvez esta resposta da primeira vista, vc tem que
1-verifique se o seu gráfico é l-colorable
2-Pesquisa por uma cor com um conjunto de vértices K