Alguém já viu um problema de gráfico NP como este antes?

Question

Eu tenho um seguinte problema baseado em gráfico:

1. Entrada:inteiros positivos K e L, gráfico não direcionado G
2. Eu tenho que escolher K vértices deste gráfico
3. 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.

Answer 1

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.

Answer 2

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.

Answer 3

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