Qualcuno ha visto un problema grafico NP come questa prima?

Question

Ho un problema seguente grafico:

.
1. Input: interi positivi K e L, grafico non rilevato G
2. Devo scegliere i vertici da questo grafico
3. Nel percorso tra ogni coppia di vertici prescelti che ci deve essere almeno i vertici, io.e.Deve esserci uno "spazio tra" ogni due di vertici scelti da almeno i vertici.

Quanto sopra, naturalmente, potrebbe non essere possibile per una determinata istanza di un problema, allora devo verificarlo.Sono abbastanza sicuro che questo problema sia NP o anche NP-Complete, poiché ha a che fare con i percorsi con vincolo della lunghezza.Hai mai incontrato un problema simile?Hai un'idea come ridurlo ad un problema più noto, possibilmente NP, E.g.Copertura vertice o Colorazione del grafico?

Inoltre, nota che il mio grafico è un grafico a griglia, che potrebbe non essere "pieno" ma un sottogramma di una griglia rettangolare completa.

Answer 1

È noto come distanza- $ D $ set indipendente, cioè, stai cercando un set indipendente di dimensioni $ k $ dove la distanza tra ogni due elementi nella soluzione è almeno $ d $ .

Il problema è NP-Completo anche sui grafici planare secondo [1], ma non conosco la sua complessità su griglie parziali.

Per quanto riguarda le riduzioni, probabilmente è possibile prendere la $ d $ 'th Potenza del grafico e trova un set indipendente (distanza-1) indipendente in questo. Il reclamo è che qualsiasi soluzione qui è una distanza- $ d $ set indipendente nell'originale, ma è necessario verificare questo.

---

.

[1] ETO, Hiroshi, Fengrui Guo ed Eiji Miyano. "Distanza- $ D $ Problemi di set indipendenti per i grafici bipartite e chordali." Journal of Combinatorial Optimization 27, n. 1 (2014): 88-99.

Answer 2

Nel caso speciale in cui $ l= 1 $ , questo è il PROBLEMA SET INDIPENDENTE MASSIMO , CHE È NP-HARD SUL GRAFICO GRANDI. Pertanto, il tuo problema è NP-HARD anche sui grafici generali.

Potresti provare a sperare per un algoritmo specifico per la classe di grafici che hai (penso che il set massimo indipendente può essere calcolato in modo efficiente nei grafici bipartite e i grafici della griglia sono bipartito, in modo da poter provare a generalizzare quell'algoritmo), oppure è possibile provare a utilizzare un algoritmo standard per il massimo set / clique indipendente o potresti provare a usare un sabato risolutore. Dovrebbe essere facile formulare questo come un'istanza MAXSAT: si ha una clausola per ogni coppia di vertici che si trovano a distanza $ l + 1 $ (o meno), e Chiedi al risolutore SAT di ridurre al minimo il numero di variabili impostato su TRUE.

Answer 3

Sembra il controllo se c'è un sottogramma K-vertices di G che è colorato utilizzando le regole del problema della colorazione del grafico.Voglio dire se tutti i vertici K sono colorati con lo stesso colore che soddisfano la tua condizione.

Poiché il grafico colorante in NP-COMPLETO U può verificare una determinata soluzione in tempo polinomiale.

Così forse, forse forse questo è una prima risposta a una prima vista, devi

1-Controlla se il tuo grafico è L-Colorable

2-Ricerca di un colore con un set di verti k