Hat jemand ein NP-Diagrammproblem so gesehen?

Question

Ich habe ein folgendes grafisches Problem:

.
1. Input: Positive Ganzzahlen K und L, ungerichtete Grafik G
2. Ich muss K-Eiter aus dieser Grafik auswählen
3. Im Pfad zwischen jedem Paar ausgewählten K-Scheitelpunkten muss mindestens l-Scheitelpunkte sein, ich.e.Es muss ein "Raum zwischen" zwischen den beiden ausgewählten Scheitelpunkten aus mindestens l-Scheitelpunkten geben.

Das oben genannte ist natürlich möglicherweise nicht für eine gegebene Instanz eines Problems möglich, dann muss ich das überprüfen.Ich bin mir ziemlich sicher, dass dieses Problem NP oder sogar NP-komplett ist, da es mit Pfaden mit Längeneinschränkungen zu tun hat.Haben Sie jemals ein ähnliches Problem getroffen?Hast du eine Idee, wie man es auf einiger bekannteres Problem reduzieren kann, möglicherweise NP, e.G.Vertexabdeckung oder -diagrammfarbe?

auch, beachten Sie, dass mein Diagramm ein Grid-Diagramm ist, der möglicherweise nicht "voll" ist, sondern einen Untergrafik eines vollen rechteckigen Gitters.

Answer 1

Dies wird als Distance- $ D $ unabhängiges Set bekannt, dh Sie suchen einen unabhängigen Satz von Größe $ K $ Wenn der Abstand zwischen den beiden Elementen in der Lösung mindestens $ D $ ist.

Das Problem ist NP-komplett auch auf planaren Grafiken gemäß [1], aber ich weiß nicht über seine Komplexität auf Teilnetzen.

In Bezug auf Reduzierungen können Sie wahrscheinlich den $ D $ 'th Leistung des Diagramms und finden Sie ein (Entfernungs-1) unabhängiges Set. Die Behauptung ist, dass eine beliebige Lösung hier ein Distanz- $ D $ unabhängig im Original ist, aber Sie müssen dies überprüfen.

---

[1] EtO, Hiroshi, Fengrui Guo und Eiji Miyano. "Distanz $ D $ Unabhängige Setprobleme für Bippartite- und Akkorddiagramme." Journal der kombinatorischen Optimierung 27, nein. 1 (2014): 88-99.

Answer 2

im Sonderfall, in dem $ l= 1 $ , ist dies der maximales unabhängiges Setproblem , das auf allgemeinen Diagrammen np-farbig ist. Daher ist Ihr Problem auch auf allgemeinen Graphen np-farbig.

Sie könnten versuchen, auf einen Algorithmus zu hoffen, der spezifisch für die Klasse der Grafiken ist, die Sie haben (ich denke, das maximale unabhängige Set kann effizient in bipartiten Diagrammen berechnet werden, und Gitterdiagramme sind zweifellos, so dass Sie versuchen, diesen Algorithmus zu verallgemeinern), oder Sie können versuchen, einen Standardalgorithmus für maximal unabhängige Set / Clique zu verwenden, oder Sie können versuchen, einen Sat zu verwenden Löser. Es sollte leicht sein, dies als MAXSAT-Instanz zu formulieren: Sie haben eine Klausel für jedes Paar von Scheitelpaaren, die sich in der Entfernung $ l + 1 $ (oder weniger) befinden, und Sie fragen den Sat-Solver, um die Anzahl der auf true eingestellten Variablen zu minimieren.

Answer 3

scheint wie zu prüfen, ob ein K-Eck-Subgraph von G, das mit den Regeln des Diagrammfärbungsproblems lk färbbar ist.Ich meine, wenn alle K-Scheitelpunkte mit der gleichen Farbe gefärbt sind, erfüllen sie Ihren Zustand.

Da die Diagrammfärbung in NP-Complete U eine gegebene Lösung in der Polynomzeit überprüfen kann.

vielleicht, vielleicht, vielleicht ist dies eine erste Sichtantwort, Sie müssen

1-Check Wenn Ihr Diagramm l-farbbar ist,

2-Suchen nach einer Farbe mit einem Satz K-Scheitelpunkte