Parametrisierte Komplexität von P nach NP-hart und wieder zurück

Ich suche nach Beispielen für Probleme, die durch eine Zahl parametrisiert sind , wobei die Härte des Problems in nicht monoton ist . Die meisten Probleme (meiner Erfahrung nach) haben einen einphasigen Übergang, zum Beispiel hat SAT einen einphasigen Übergang von (wo das Problem in P ist) zu (wo die Problem ist NP-vollständig). Ich interessiere mich für Probleme, bei denen es Phasenübergänge in beide Richtungen gibt (von leicht nach hart und umgekehrt), wenn zunimmt. k k k ≤ { 1 , 2 } k ≥ 3 $k \in \mathbb{N}$$k$$k$$k \in \{1,2\}$$k \ge 3$$k$

Meine Frage ist der bei Härtesprünge in der rechnerischen Komplexität gestellten etwas ähnlich , und tatsächlich sind einige der Antworten dort für meine Frage relevant.

Beispiele, die mir bekannt sind:

1. k = $k$ Färbbarkeit planarer Graphen: In P, außer wenn , wo es NP-vollständig ist.$k=3$
2. Steinerbaum mit Anschlüssen: In P, wenn (kollabiert zum kürzesten - Pfad) und wenn (kollabiert zum MST), aber NP-hart "dazwischen". Ich weiß nicht, ob diese Phasenübergänge scharf sind (z. B. P für aber NP-hart für ). Auch die Übergänge von hängen im Gegensatz zu meinen anderen Beispielen von der Größe der Eingabeinstanz ab.k = 2 s t k = n k 0 k 0 + 1 $k$$k=2$$s$$t$$k=n$$k_0$$k_0+1$$k$
3. Zählen zufriedenstellender Zuordnungen einer planaren Formel modulo : In P, wenn eine Mersenne- Primzahl ist, ist und # P-vollständig für die meisten (?) / Alle anderen Werte von (von Aaron Sterling in diesem Thread) ). Viele Phasenübergänge!n n = 2 k - 1 $n$$n$$n=2^k-1$$n$
4. Induzierte Subgraphenerkennung: Das Problem wird nicht durch eine Ganzzahl, sondern durch einen Graphen parametrisiert. Es gibt Graphen (wobei eine bestimmte Art von Untergraphenrelation bezeichnet), für die bestimmt wird, ob für einen gegebenen Graphen in P für aber NP-vollständig für . (von Hsien-Chih Chang im selben Thread ). ≤ H i ≤ G G i ≤ { 1 , 3 } i = $H_1 \subseteq H_2 \subseteq H_3$$\subseteq$$H_i \subseteq G$$G$$i\in \{1,3\}$$i=2$

Ein Bereich mit vielen nicht monotonen Aspekten der Problemkomplexität ist das Testen von Eigenschaften. Sei die Menge aller -Vertex-Graphen und bezeichne als Grapheneigenschaft. Ein generisches Problem besteht darin, zu bestimmen, ob ein Graph die Eigenschaft (dh ) oder in gewissem Sinne von der Eigenschaft weit entfernt ist . Abhängig davon, was ist und welche Art von Abfragezugriff Sie auf das Diagramm haben, kann das Problem sehr schwierig sein. nP⊆ G n GPG∈PP$\mathcal{G}_n$$n$$P \subseteq \mathcal{G}_n$$G$$P$$G \in P$$P$$P$

Es ist jedoch leicht zu erkennen, dass das Problem nicht monoton ist, da, wenn wir , die Tatsache, dass leicht testbar ist, nicht impliziert, dass leicht testbar ist oder dass ist. P S $S \subset P \subset T$$P$$S$$T$

Um dies zu sehen, ist es ausreichend zu beobachten, dass und beide trivial testbar sind, aber dass für einige Eigenschaften starke Untergrenzen existieren. P = $P = \mathcal{G}_n$$P = \emptyset$

Für einen gegebenen Graphen und eine ganze Zahl k ≥ 1 hat die mit G k bezeichnete k- te Potenz von G die gleiche Scheitelmenge, so dass zwei verschiedene Scheitelpunkte in G k benachbart sind, wenn ihr Abstand in G höchstens k beträgt . Das Problem der k- ten Potenz eines geteilten Graphen fragt, ob ein gegebener Graph die k- te Potenz eines geteilten Graphen ist.$G$$k\ge 1$$k$$G$$G^k$$G^k$$G$$k$$k$$k$

• Für ist das Problem in linearer Zeit lösbar. Dies liegt daran, dass das Erkennen von geteilten Diagrammen in linearer Zeit möglich ist (allgemein bekannt).$k=1$
• Für ist das Problem NP-vollständig. Dies wird von Lau und Corneil in Recognition powers of proper interval, split und chordal graph , SIAM J. Discrete Math., 18 (2004), 83-102, bewiesen .$k=2$
• Für ist das Problem trivial: Nur vollständige Graphen sind te Potenzen eines geteilten Graphen.$k\ge 3$$k$

Eines dieser Probleme ist die Kantenfärbung von ebenen Graphen, bei denen der Parameter - maximaler Grad eines Graphen ist. Wenn oder gibt es dafür bekannte Algorithmen ( siehe hier ), wohingegen für solche Algorithmen nicht bekannt sind und es für diese Fälle keine NP-Härte-Beweise gibt .$\Delta$$\Delta=2$$\Delta\geqslant 7$$3\leqslant\Delta\leqslant 6$

Die zugehörige Frage wird hier diskutiert .

Bestimmen, ob ein Graph eine dominierende Clique hat für:$G$

• $diam(G)=1$ ist trivial - die Antwort lautet immer "ja"
• $diam(G)=2$ ist NP-vollständig
• $diam(G)=3$ ist NP-vollständig
• $diam(G)\ge 4$ ist trivial - die Antwort lautet immer 'nein'

Der Fall geht auf Brandstädt und Kratsch zurück , und der Fall ist in einer meiner jüngsten vermerkt .d i a m ( G ) = $diam(G)=3$$diam(G)=2$

Ist dies ein Beispiel für das Phänomen, nach dem Sie suchen?

Betrachten Sie das k-Clique-Problem, wobei k die Größe der Clique ist, nach der wir suchen. Das Problem ist also: "Gibt es eine Clique der Größe k im Graphen G auf n Eckpunkten?"

Für alle Konstanten k liegt das Problem in P. (Der Brute-Force-Algorithmus läuft in der Zeit .) Für große Werte von k, zum Beispiel Werte wie n / 2, ist es NP-vollständig. Wenn k n sehr nahe kommt, wie nc für eine Konstante c, liegt das Problem wieder bei P, da wir alle Teilmengen von n Knoten der Größe nc durchsuchen und prüfen können, ob einer von ihnen eine Clique bildet. (Es gibt nur solcher Teilmengen, die polynomiell groß sind, wenn c eine Konstante ist.)O ( n c$O(n^k)$$O(n^c)$

Hier ist ein Beispiel für den Typ, den Sie suchen. Der Parameter ist jedoch keine Ganzzahl, sondern ein Zahlenpaar. (Obwohl einer von ihnen behoben werden kann, um es zu einem Ein-Parameter-Problem zu machen.)

Das Problem besteht darin, das Tutte-Polynom eines Graphen G bei Koordinaten (x, y) auszuwerten. Wir können die Koordinaten auf ganze Zahlen beschränken. Das Problem liegt in P, wenn (x, y) einer der Punkte (1, 1), (-1, -1), (0, -1), (-1,0) ist oder (x-1) erfüllt ) (y-1) = 1. Ansonsten ist es # P-schwer.

Ich habe dies aus dem Wikipedia-Artikel über das Tutte-Polynom erhalten .

Was ist mit der Frage der permanenten einer Matrix Modulo Berechnung ? Für dies einfach (da permanent = determinant), und Valiant (in " Die Komplexität der Berechnung der permanenten ") zeigte, dass es modulo in der Zeit für berechnet werden kann durch eine modifizierte Variante der Gaußschen Elimination. Aber für das keine Potenz von , ist es UP-Hard. k = 2 2 d O ( n 4 d - 3 ) d ≥ 2 k $k$$k=2$$2^d$$O(n^{4d-3})$$d \geq 2$$k$$2$

Ein weiteres Problem bei diesem Phänomen ist das MINIMUM -SPANNER-Problem bei geteilten Diagrammen.$t$

Für eine Konstante ist ein Spanner eines zusammenhängenden Graphen ein zusammenhängender überspannender Teilgraph von so dass für jedes Paar von Eckpunkten und der Abstand zwischen und in höchstens das fache ihres Abstandes in beträgt . Das MINIMUM -SPANNER-Problem fordert einen -Spanner mit einer minimalen Anzahl von Kanten eines gegebenen Graphen an.t G H G x y x y H t G t $t$$t$$G$$H$$G$$x$$y$$x$$y$$H$$t$$G$$t$$t$

Ein geteiltes Diagramm ist ein Diagramm, dessen Scheitelpunktmenge in eine Clique und eine unabhängige Menge unterteilt werden kann.

In diesem Papier wurde gezeigt , dass mindestens 2-SPANNER auf Split Graphen ist NP-hart , während für jeden , MINDEST -SPANNER auf Split Graphen einfach.$t \ge 3$$t$

Bekanntes Beispiel ist die Kantenfärbung.$k$

Es ist in der Polynomzeit entscheidbar, ob andernfalls ist es vollständig .N P$k \ne \Delta$$NP$

Entscheiden Sie bei kubischen Diagrammen, ob Kantenfarben vorhanden sind, indem Sie Folgendes verwenden:

• $k=2$ Farben ist trivial, da die Antwort immer nein lautet.
• N $k=3$ Farben ist vollständig$NP$
• $k \ge 4$ Farben ist trivial, da die Antwort immer ja ist.

Holyer, Ian (1981), "Die NP-Vollständigkeit der Kantenfärbung", SIAM Journal on Computing 10: 718–720

http://en.wikipedia.org/wiki/Edge_coloring

Dies ist ein interessantes (und überraschendes) Beispiel für einen Phasenübergang von P NP-hart P NP-hart :$\to$$\to$$\to$$\to \cdots$

Die Entscheidung, ob ein vollständiger Graph für Scheitelpunkte, in dem jeder Scheitelpunkt eine strenge Rangfolge aller anderen Scheitelpunkte aufweist, eine beliebte Übereinstimmung zulässt, ist in P für ungerade und NP-schwer für gerade . (Der Parameter ist die Scheitelpunktnummer .)$n$$n$$n$$n$

Der Beweis wurde in diesem Papier angekündigt .

Ein Pfad in einem kantenfarbenen Diagramm ist ein Regenbogen, wenn keine Farbe zweimal darauf erscheint. Ein Diagramm ist regenbogenfarben, wenn zwischen jedem Scheitelpunktpaar ein Regenbogenpfad liegt. Lassen Sie RAINBOW- COLORABILITY das Problem sein, zu entscheiden, ob ein gegebenes Diagramm mit Farben regenbogenfarben sein kann .$k$$k$

Für jeden Graphen ist das Problem für einfach, da es der Überprüfung entspricht, ob ein vollständiger Graph ist. Für geteilte Graphen ist das Problem -complete für und in für alle anderen Werte von .k = 1 G N P k ∈ { 2 , 3 } P $G$$k=1$$G$$\sf NP$$k \in \{2,3\}$$\sf P$$k$

Siehe Chandran, L. Sunil, Deepak Rajendraprasad und Marek Tesař. "Regenbogenfärbung von geteilten Graphen." arXiv-Vorabdruck arXiv: 1404,4478 (2014).

Eine Teilmenge eines Graphen ist eine nicht verbundene Teilmenge, wenn und sind.G G [ U ] G - $U\subseteq V(G)$$G$$G[U]$$G-U$

Es ist unerheblich, ob in einem Diagramm mit Durchmesser 1 ein nicht verbundenes Cutset vorliegt. Das Problem wird bei Diagrammen mit einem Durchmesser von 2 NP-hart ( siehe dieses Papier) und bei Diagrammen mit einem Durchmesser von mindestens 3 NP-hart ( siehe dieses Papier) .