¿Alguien ha visto un problema gráfico de NP como este antes?

Question

Tengo un siguiente problema basado en gráfico:

1. entrada: enteros positivos k y l, gráfico no dirigido g
2. Tengo que elegir k vértices de este gráfico
3. En el camino entre cada par de vertices K elegidos, tiene que haber al menos vértices, i.mi.Tiene que haber un "espacio entre" cada dos de los vértices elegidos hechos de al menos l vértices.

El anterior, por supuesto, puede que no sea posible para una instancia determinada de un problema, entonces tengo que comprobarlo.Estoy bastante seguro de que este problema es NP o incluso NP-Completa, ya que tiene que ver con los caminos con restricción de longitud.¿Alguna vez has conocido un problema similar?¿Tienes una idea de cómo reducirlo a un problema más conocido, posiblemente NP, E.gramo.¿Funda de vértice o colorante gráfico?

Además, tenga en cuenta que mi gráfica es un gráfico de cuadrícula, que podría no estar "completo" sino un subgrógrafo de una cuadrícula rectangular completa.

Answer 1

Esto se conoce como la distancia- $ d $ Conjunto independiente, es decir, está buscando un conjunto independiente de tamaño $ k $ donde la distancia entre cada dos elementos en la solución es al menos $ d $ .

El problema es NP: completo incluso en gráficos planos de acuerdo con [1], pero no sé sobre su complejidad en cuadrículas parciales.

Respecto a las reducciones, probablemente puede tomar el $ d $ 'th Potencia del gráfico y encuentra un conjunto independiente (Distancia-1) Independiente en eso. La reclamación es que cualquier solución aquí es una distancia- $ d $ independiente establecido en el original, pero necesita verificar esto.

---

[1] Eto, Hiroshi, Fengrui Guo, y Eiji Miyano. "Distancia- $ d $ Independent establece problemas para los gráficos bipartitos y cordales". Diario de la optimización combinativa 27, no. 1 (2014): 88-99.

Answer 2

En el caso especial donde $ l= 1 $ , este es el Problema de conjunto máximo independiente , que es NP-DURS en los gráficos generales. Por lo tanto, su problema también es NP-HARD en los gráficos generales.

Podría intentar esperar un algoritmo que sea específico de la clase de gráficos que tiene (creo que el conjunto máximo independiente se puede calcular de manera eficiente en gráficos bipartitos , y los gráficos de la cuadrícula son bipartitos, por lo que podría intentar generalizar ese algoritmo), o podría intentar usar un algoritmo estándar para un conjunto / clique independiente máximo, o podría intentar usar un SAT solucionador Debe ser fácil formular esto como una instancia de MaxSat: tiene una cláusula para cada par de vértices que están dentro de distancia $ l + 1 $ (o menos), y Usted le pide al solucionador SAT que minimice el número de variables establecidas en VERDADERO.

Answer 3

Parece que compruebe si hay un subgrafo de K-vértices de G que es colorible usando las reglas del problema de coloración de gráficos.Quiero decir, si todos los vértices k se colorean con el mismo color, satisfacen su condición.

Dado que el gráfico se colorea en NP-Complete U puede verificar una solución dada en el tiempo de polinomio.

así que tal vez, tal vez esta una primera respuesta de la vista, u tiene que

1-compruebe si su gráfico es L-colorable

2-búsqueda de un color con un conjunto de k vértices