Komplexität des Digraphenhomomorphismus zu einem orientierten Zyklus

Bei einem fest gerichteten Graphen (Digraphen) fragt $D$das $D$ COLORING-Entscheidungsproblem, ob ein Eingangsdigraph $G$ einen Homomorphismus zu $D$ . (Ein Homomorphismus von $G$ zu $D$ ist eine Abbildung $f$ von $V(G)$ auf $V(D)$ , die die Bögen bewahrt, dh wenn $uv$ ein Bogen von $G$ , dann ist $f(u)f(v)$ ein Bogen von $D$ )

Die Klasse der $D$ FARBEN-Probleme ist stark mit der Dichotomie-Vermutung für CSPs verbunden , die von Feder und Vardi angegeben wurde (zugänglich für Citeseer ).

In diesem 2001 Papier (zugänglich auf der Seite des Autors hier ), beweist Feder ein Dichotomie Theorem , wenn$D$ ein orientierter Zyklus (vonorientierten Zyklusmeine ich eine ungerichtete Zyklusdem jede Kante durch einen einzigen Bogen ersetzt, die beliebig ausgerichtet werden können) , mit anderen Worten, zeigt erdass für jede orientierte Zyklus$D$ ,$D$ -COLORING ist entweder Polynomialzeit lösbar oder NP-vollständig.

Leider ist die Klassifizierung von Feder höchst nicht trivial und nicht explizit, da die Komplexität vieler Fälle mit der Komplexität bestimmter eingeschränkter Varianten von SAT zusammenhängt, die von der Ausrichtung abhängen. Durch einen Blick auf das Papier konnte ich die Antwort auf meine Frage nicht feststellen:

Frage: Was ist die kleinste Größe eines orientierten Zyklus $D$ so dass $D$ FARBE NP-vollständig ist?

Die Antwort könnte irgendwo in der Literatur angegeben sein, aber ich konnte sie nicht finden.

Bearbeiten:Lassen Sie mich näher auf die Klassifizierung von Feder eingehen. Feder zeigt, dass jeder NP-vollständig orientierte Zyklus ausgeglichen sein muss, dh die gleiche Anzahl von Bögen in beide Richtungen haben muss (daher hat er eine gerade Ordnung). Betrachten Sie dann die durch die Ausrichtung induzierten "Ebenen" (beginnen Sie, den Zyklus an einem beliebigen Scheitelpunkt zu umgehen; wenn ein Bogen nach rechts geht, steigen Sie um 1, wenn ein Bogen nach links geht, gehen Sie um 1 nach unten). Wenn es dann höchstens einen "Top-Bottom-Lauf" gibt, ist dies ein Polynom. Wenn es mindestens 3 solcher "Läufe" gibt und der Zyklus ein Kern ist, ist er NP-vollständig. (In András 'Beispiel aus den Kommentaren gibt es drei solcher "Läufe", aber der Zyklus ist kein Kern.) Die schwierigsten Fälle sind solche mit zwei "Top-Bottom-Läufen". Einige sind hart, andere polynomisch, und Feder bezieht sie auf spezielle SAT-Probleme, um eine Dichotomie zu erhalten.

Als Zwischenfrage: Was ist der kleinste orientierte Zyklus, der drei "Top-Bottom" -Läufe hat und ein Kern ist? Ein solches Beispiel wäre durch die obige Diskussion NP-vollständig.

Wie wäre es mit der Zwischenfrage (einem Kern mit drei Top-Bottom-Läufen)?

Einige Notationen: Ich werde Läufe durch Wörter in , wobei z. B. l l r l einem Untergraphen ⋅ ← ⋅ ← ⋅ → ⋅ ← ⋅ entspricht . Der Pegel steigt bei r Bögen an und sinkt bei l Bögen, und ich gehe davon aus, dass sein Minimum 0 ist . Einige einfache Einschränkungen sind:$\{l,r\}^*$$llrl$$\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$$r$$l$$0$

• Es kann keinen Lauf geben, der nur aus oder nur aus rs besteht , da ansonsten ein offensichtlicher Homomorphismus von D zu diesem Lauf besteht (Zuordnung jedes Knotens von D zu dem Knoten mit demselben Pegel). Dies bedeutet auch, dass der maximale Pegel mindestens 3 betragen muss$l$$r$$D$$D$$3$ .
• Wenn das maximale Niveau , hätten alle Läufe von oben nach unten (bzw. von unten nach oben) die Form l l r ( l r ) i l l (bzw. r r l ( r l ) i r r ) ; wieder ist es nicht sehr schwer, einen Homomorphismus von D zum Lauf zu finden , der i minimiert .$3$$llr(lr)^ill$$rrl(rl)^irr)$$D$$i$

Jedoch für maximales Niveau gibt es eine Lösung, mit einer Länge von 36 : Betrachten D gegeben durch ( r r r l r r l l l r l l ) $4$$36$$D$$(rrrlrrlllrll)^3$ . Dies hat die erforderlichen Top-Bottom-Läufe und ist ein Kern (siehe unten). Durch die obigen Einschränkungen ist es notwendigerweise minimal, da jeder Lauf nur eine einzige "Rückwärts" -Kante hat.

Um uns davon zu überzeugen, dass dies ein Kern ist, nennen wir zuerst die Eckpunkte ( ). Die unteren Eckpunkte (dh Ebene 0 ) sind v 1 , v 13 , v 25 . Jeder Homomorphismus φ von D zu einem Teilgraphen muss Ebenen bewahren, insbesondere φ ( v 1 ) ∈ { v 1 , v 13 , v 25 } ; Modulo der offensichtliche Automorphismus v i$v_1,\ldots,v_{36}$$0$$v_1,v_{13},v_{25}$$\varphi$$D$$\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$ es aus, den Fallφ( v 1 )= v 1 zu betrachten . Betrachten Sie die Nachbarschaft von v 1 inD(mit Ebenen versehen):$v_i\mapsto v_{i+12}$$\varphi(v_1)=v_1$$v_1$$D$

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Beginnend mit haben wir φ ( v 2 ) ∈ { v 36 , v 2 } . Aber wenn φ ( v 2 ) = v 36 ist , dann ist φ ( v 3 ) = v 35 , und wir haben keinen möglichen Wert für φ ( v 4 ) . Wir erhalten φ ( v 2 ) = $\varphi(v_1)=v_1$$\varphi(v_2)\in\{v_{36},v_2\}$$\varphi(v_2)=v_{36}$$\varphi(v_3)=v_{35}$$\varphi(v_4)$ . Als nächstes ist φ ( v 5 ) ∈ { v 3 , v 5 } , aber für φ ( v 5 ) = v 3 erhalten wir φ ( v 6 ) = v 4 , ohne einen möglichen Wert für φ ( v 7 ) . So$\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$$\varphi(v_5)\in\{v_3,v_5\}$$\varphi(v_5)=v_3$$\varphi(v_6)=v_4$$\varphi(v_7)$ die Identität auf die gesamte Auflage sein muss , v 1 → ... → v 7 und durch das gleiche Argument für die verbleibenden Läufe wiederholen, ist das gleiche auf allen wahren D . Insbesondere ordnet φ D nichteinem richtigen Untergraphen zu.$\varphi$$v_1\to\ldots\to v_7$$D$$\varphi$$D$