Natural CLIQUE zur k-Farbreduktion

23

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 vu und ( cd oder vuG ). Eine n Klasse in Ghat 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 kG,kG¯nk+1kGkG v1,,vnG¯Cij1in0jk. 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 ) jC ( i - 1 ) ( j - 1 )Cij{v1,,vi}jCi0Cijj>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(i1)jC(i1)(j1)vikGCnkk

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.Knk+1viCij

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?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.

William Macrae
quelle
4
Die Art der direkten Reduktion, nach der Sie suchen, ist möglicherweise schwer zu finden, da Clique und Färbung insofern gegensätzlich sind, als eine 1-Clique genauso leicht zu finden ist wie eine n-Färbung. Vielleicht sollte die Reduktion der Form: hat eine n - k -coloring , wenn und nur wenn G einen hat k -cliqueGnkGk
Martin Vatshelle
Ich stimme zu, dass es schwierig ist; das ist der Grund für mein Interesse; Ich werde auf die Motivation in der Frage näher eingehen. Die Idee -coloring hat mir am nächsten gekommen. Wenn es eine ist k -clique in G dann ¯ G haben alle Knoten in der Clique monochromatische können , weil sie eine unabhängige Menge sind. Das Problem ist, dass die chromatische Zahl des Rests variieren kann. Wenn Sie zwei Scheitelpunkte mit einem K n - k - 1 verknüpfen, werden sie in derselben Farbe angezeigt, aber ich habe keine Ahnung, welche Scheitelpunkte erzwungen werden sollen. Ein Gerät, das einige i aus j zwingtnkkGG¯Knk1ijVertices, die monochromatisch sind, würden es tun.
William Macrae
3
Ich stimme hier mit Martin überein, dass dies möglicherweise nicht einmal machbar ist (ohne über 3SAT zu gehen). Clique und Färbung haben sehr wenig gemeinsam. Ich möchte daher an den Satz von Erdős erinnern, wenn man die Naturwerte g und k annimmt, gibt es einen Graphen mit einem Umfang von mindestens g und einer chromatischen Zahl von mindestens k (denken Sie eine Weile darüber nach, wenn Sie nicht damit vertraut sind). Schließlich muss Ihrer Reduktion auch bewusst sein, dass es keine äquivalente Parametrisierung für die chromatische Zahl eines Graphen gibt , während Clique (und Independent Set) in durch den Lösungssatz parametrisiert ist. W[1]
Pål GD,
Ich verstehe den Kommentar von @ MartinVatshelle nicht. Soweit ich weiß, sind alle 1-Clique-, 1-Coloring-, n-Clique- und n-Coloring-Elemente auf demselben Niveau. (Denken Sie nicht, dass Sie die 1-Clique immer mit JA beantworten können: Der Eingabediagramm ist möglicherweise leer!)
Yixin Cao
Ich denke, Martins Punkt ist, dass es Show und χ ( G ) = 3 ist , aber es ist schwieriger, eine K 4 als eine K 3 zu finden . Die beiden Konzepte haben also eine gewisse Dualität. Der Punkt von @ PålGD zu Erdős Theorem ist großartig (und ich liebe diesen Theorem), da Graphen mit großem Umfang eine große Unabhängigkeitszahl haben und ihre Inversen daher große Cliquen haben. Insgesamt scheint es hier eine Falle zu geben, die Cliques und Colorings in denselben oder ähnlichen Graphen in Beziehung setzt, aber wie bei der umgekehrten Richtung kann die Reduktion einen ganz anderen Graphen als G konstruieren .χ(G)=4χ(G)=3K4K3G
William Macrae

Antworten:

14

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:GkGkGHHnGk

(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 .vGn(v,i)Hi1n

(2) In einem weiteren Scheitelpunkt zu H .xH

(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 ) k{x,y,z}Hy=(v,i)z=(u,j)uvi=juvGmax(i,j)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 .xyzHGH(v,i)xik

David Eppstein
quelle
2
This is wonderful.
William Macrae
For some reason my edit was rejected, but the last sentence should describe vertices of G rather than H (since it is intended to describe a clique in G). Something like "The clique in G can be recovered from a coloring of H as {v:ikχ((v,i))=χ(x)}." Also, I forgot to say thanks for the answer, it's been very helpful!
William Macrae
Sure, you could put in another clause to that sentence about stripping off the i from each pair, but I thought that step was easy enough to omit, and my general feeling is that (when it can be kept short enough) prose tends to be more readable than a formula.
David Eppstein
I agree that prose are more preferable. Maybe just adding a phrase like "the first coordinate of each (v,i)..." is idea. The reason for my concern about the technicality is that when first reading reductions it can be hard to keep straight the exact definitions of the elements in the first language and the second, and which is which. The minute something appears to break a definition, it can throw me for a loop. If I had trouble understanding previous sentences and got to the last one, I would determine that G and H have vertices of the form (v,i).
William Macrae
I should also say that I think you've done a much better job talking through this reduction than almost any other that I've read. There's a problem in the literature that many reductions are stated formally with no motivation or intuition, and you've avoided that very nicely.
William Macrae
-7

?? 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: χ(G)ω(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

vzn
quelle
5
Using the property χ(G)ω(G), you can invoke an algorithm for kCOLORABILITY on G: if the algorithm returns YES, then G does not contain any clique of size at least k+1. However the opposite implication does not hold: if the algorithm returns NO, then G may or may not have a clique of size at least k+1 (as a counterexample, consider a pyramid whose polygonal base has an odd number of vertices: it is not 3-colorable, however it has not any clique of size at least 4).
Giorgio Camerani
yes, agreed; as I interpret it the original post was not insistent on the direction of the reduction but more emphasized avoiding SAT as the intermediary, asking for a "fairly brief explanation". also conspicuously nobody mentioned the above factoid so far.... the question & comments also seem to inaccurately indicate in various ways the two problems are not tightly coupled....
vzn
1
Apologies if the direction was ambiguous. I am interested in a correct reduction (YES YES), and I am interested in a reduction from Clique to k-Color. I have the other direction and it is explained in my post. There are certainly many things that relate cliques in graphs to colorings in graphs and vice versa, and indeed I have seen many of them (and I assume many others here have seen many of them), but I'm really interested exclusively in a direct reduction or a convincing explanation of why it might not exist.
William Macrae
1
@vzn: My comment was not meant to criticize your answer. Truth be told, initially I made a reasoning similar to yours, but then I realized that, if the opposite implication would have hold, then 3COLORING on general graphs, which is known to be NP-complete, would have been solvable trivially by just checking whether the input graph had a clique of 4 nodes: any G would have been 3-colorable if and only if it does not contain any clique of size 4 (that's plain false, of course, as the pyramid counterexample shows). By the way: I'm not the one who downvoted.
Giorgio Camerani
3
@WilliamMacrae: It was perfectly clear that you wanted a reduction, otherwise it wouldn't have been a reduction! Also, it was perfectly clear that you wanted a reduction from CLIQUE to COLORING and not the other way.
Giorgio Camerani