Natural CLIQUE zur k-Farbreduktion

Es gibt eindeutig eine Reduzierung von CLIQUE auf k-Color, da beide NP-Complete sind. Tatsächlich kann ich einen erstellen, indem ich eine Reduktion von CLIQUE auf 3-SAT mit einer Reduktion von 3-SAT auf k-Color zusammensetze. Ich frage mich, ob es eine vernünftige direkte Reduzierung zwischen diesen Problemen gibt. Sagen wir, eine Reduktion, die ich einem Freund ziemlich kurz erklären könnte, ohne eine Zwischensprache wie SAT beschreiben zu müssen.

Als Beispiel für das, wonach ich suche, ist hier eine direkte Reduktion in umgekehrter Richtung: Wenn G mit $n$ und etwas $k$ (die Anzahl der Farben) gegeben ist, mache ein Diagramm G 'mit $kn$ Ecken (eine pro Farbe pro Ecke) . Die Eckpunkte $v'$ , $u'$ entspricht Eckpunkten $v, u$ und Farben $c, d$ sind jeweils benachbarte , wenn und nur wenn $v \neq u$ und ( $c \neq d$ oder $vu \not \in G$ ). Eine $n$ Klasse in $G'$hat nur ein Eckpunkt pro Vertex in $G$ , und die entsprechenden Farben sind ein geeigneter $k$ -coloring von $G$ . In ähnlicher Weise hat jede richtige $k$ Färbung von $G$ eine entsprechende Clique in $G'$ .

Bearbeiten : Um eine kurze Motivation hinzuzufügen, Karps ursprüngliche 21 Probleme werden durch einen Baum von Reduktionen als NP-vollständig bewiesen, wobei CLIQUE und Chromatic Number die Wurzeln der wichtigsten Teilbäume bilden. Es gibt einige natürliche Verringerungen zwischen Problemen im CLIQUE-Unterbaum und im Chromatic Number-Unterbaum, aber viele von ihnen sind genauso schwer zu finden wie die, nach denen ich frage. Ich versuche herauszufinden, ob die Struktur dieses Baums eine zugrunde liegende Struktur in den anderen Problemen aufweist oder ob es völlig eine Folge davon ist, welche Reduktionen zuerst gefunden wurden, da es weniger Motivation gibt, nach Reduktionen zwischen zwei Problemen zu suchen, wenn sie auftreten sind bekanntermaßen in der gleichen Komplexitätsklasse. Sicherlich hatte die Reihenfolge einen gewissen Einfluss, und Teile des Baums können neu angeordnet werden, aber kann sie willkürlich neu angeordnet werden?

Bearbeiten 2 : Ich suche weiterhin nach einer direkten Reduktion, aber hier ist eine Skizze der nächsten, die ich bekommen habe (es sollte eine gültige Reduktion sein, aber CIRCUIT SAT ist ein klarer Vermittler; es ist etwas subjektiv, ob dies besser ist als zwei Kürzungen gemäß Absatz 1 zusammenzustellen).

In Anbetracht , wissen wir , dass ¯ G sein kann , n - k + 1 -colored mit k Ecken alle wahren farbigen iff G einen hat k -clique. Wir nennen die ursprünglichen Scheitelpunkte G v 1 , ... , v n und fügen Sie dann ¯ G zusätzliche Scheitelpunkte : C i j mit 1 ≤ i ≤ n , 0 ≤ j ≤ $G, k$$\overline{G}$$n-k+1$$k$$G$$k$$G$ $v_1, \ldots, v_n$$\overline G$$C_{ij}$$1 \le i \le n$$0 \le j \le k$. Die Schlüsselinvariante wird sein, dass genau dann als wahr gefärbt werden kann, wenn zwischen den Eckpunkten { v 1 , … , v i } mindestens j Eckpunkte als wahr gefärbt sind. Also kann jedes C i 0 wahr sein. Dann erhält C i j für j > 0 die Farbe C ( i - 1 ) j ∨ C ( i - 1 ) ( j - 1 )$C_{ij}$$\{v_1,\ldots, v_i\}$$j$$C_{i0}$$C_{ij}$$j > 0$ wobei alle nicht zutreffenden Farben als falsch behandelt werden. Es gibt eine k- Klasse in G, wenn C n k mit True gefärbt werden kann. Wenn wir diese Färbung erzwingen, kann das neue Diagramm eingefärbt werden, wennim ursprünglichen Diagrammeine k- Klassevorhanden war.$C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$$k$$G$$C_{nk}$$k$

Die UND- und ODER-Minianwendungen zum Erzwingen der Beziehungen ähneln weitgehend der Reduzierung von CIRCUIT SAT auf 3-COLOR. Hier fügen wir jedoch ein in unser Diagramm ein, wählen die Eckpunkte T, F und Ground aus und verbinden dann alle andere zu allem außer den v i s; dies gewährleisten , dass die C i j s und die anderen Geräte nur 3 Farben erhalten.$K_{n-k+1}$$v_i$$C_{ij}$

Wie auch immer, der Teil dieser Reduktion fühlt sich direkt an, aber die Verwendung von UND / ODER-Gattern ist viel weniger direkt. Die Frage bleibt, gibt es eine elegantere Reduktion?$\overline G$

Edit 3 : Es gab ein paar Kommentare darüber, warum diese Reduzierung schwer zu finden sein würde. CLIQUE und k-Color sind in der Tat ganz unterschiedliche Probleme. Auch ohne eine Reduzierung wäre eine Antwort, die genau beschreibt, warum die Reduzierung in der einen Richtung schwierig, in der anderen jedoch möglich ist, sehr hilfreich und trägt viel zum Problem bei.

Bei einem Graphen und eine Zahl k , so dass Sie wissen wollen, ob G ein enthält k -clique, n die Anzahl der Ecken in seiner G . Wir bauen ein weiteres Diagramm , H , so dass H ist n -colorable wenn und nur wenn G einen hat k -clique, wie folgt:$G$$k$$G$$k$$G$$H$$H$$n$$G$$k$

(1) Machen Sie für jeden Scheitelpunkt in G eine n- Klasse von Scheitelpunkten ( v , i ) in H , wobei i von 1 bis n reicht .$v$$G$$n$$(v,i)$$H$$i$$1$$n$

(2) In einem weiteren Scheitelpunkt zu H .$x$$H$

(3) Testen Sie für jedes Dreifache von Eckpunkten in H , wobei y = ( v , i ) und z = ( u , j ) , ob eine der folgenden Bedingungen zutrifft: entweder u ≠ v und i = j oder u und v sind nicht benachbarte Eckpunkte in G mit max ( i , j ) ≤ $\{x,y,z\}$$H$$y=(v,i)$$z=(u,j)$$u\ne v$$i=j$$u$$v$$G$$\max(i,j)\le k$. If either of these two things is true, add another $n$-clique to $H$. Within this clique, select three vertices $x'$, $y'$, and $z'$. Connect $x$ to every vertex in the clique except for $y'$ and $z'$; connect $y$ to every vertex in the clique except for $x'$ and $z'$; and connect $z$ to every vertex in the clique except for $x'$ and $y'$.

Die in Schritt (3) hinzugefügten Minianwendungen verhindern, dass das Dreifache der Scheitelpunkte , y und z in einer gültigen Färbung von H die gleiche Farbe erhält . Die Clique in G kann aus einer Färbung von H als der Menge von Scheitelpunkten ( v , i ) gewonnen werden , die in derselben Farbklasse wie x liegen und i ≤ k haben .$x$$y$$z$$H$$G$$H$$(v,i)$$x$$i\le k$

?? coloring and clique finding have been known to be tightly coupled for decades via graph theory (possibly even in the 60s?) even not through SAT as an intermediary (which became typical after the Cook proof in 1971). believe there are algorithms based on the following basic property:

If G contains a clique of size k, then at least k colors are needed to color that clique; in other words, the chromatic number is at least the clique number: $\chi(G) \ge \omega(G).\,$

not sure of exact refs but [1,2] are good places to start, an exact algorithm or ref is at least likely cited in these books.

[1] Cliques, coloring, & satisfiability, 2nd DIMACS challenge

[2] Dimacs vol 26: Cliques, coloring and satisfiability