CLIQUE naturelle à la réduction k-Color

Il y a clairement une réduction de CLIQUE à k-Color car ils sont tous deux NP-Complete. En fait, je peux en construire un en composant une réduction de CLIQUE à 3-SAT avec une réduction de 3-SAT à k-Color. Je me demande s'il y a une réduction directe raisonnable entre ces problèmes. Disons, une réduction que je pourrais expliquer à un ami assez brièvement sans avoir besoin de décrire un langage intermédiaire comme SAT.

À titre d'exemple de ce que je recherche, voici une réduction directe dans le sens inverse: étant donné G avec et certains (le nombre de couleurs), faites un graphique G 'avec sommets (un par couleur par sommet). Les sommets , correspondant respectivement aux sommets et aux couleurs sont adjacents si et seulement si et ( ou ). Une -clique dans n'a qu'un sommet par sommet dans , et les couleurs correspondantes sont une coloration appropriée de $n$ $k$ $kn$ $v'$ $u'$ $v, u$ $c, d$ $v \neq u$ $c \neq d$ $vu \not \in G$ $n$ $G'$ $G$ $k$ $G$ . De même, tout coloriage approprié de a une clique correspondante dans . $k$ $G$ $G'$

Edit : Pour ajouter une brève motivation, les 21 problèmes originaux de Karp sont prouvés NP-Complete par un arbre de réductions où CLIQUE et Chromatic Number forment les racines des principaux sous-arbres. Il existe des réductions naturelles entre les problèmes dans le sous-arbre CLIQUE et le sous-arbre Chromatic Number, mais beaucoup d'entre eux sont tout aussi difficiles à trouver que celui sur lequel je pose la question. J'essaie de savoir si la structure de cet arbre montre une structure sous-jacente dans les autres problèmes ou si c'est entièrement une conséquence des réductions qui ont été trouvées en premier, car il y a moins de motivation à rechercher des réductions entre deux problèmes quand ils sont connus pour être dans la même classe de complexité. Certes, l'ordre a eu une certaine influence, et des parties de l'arbre peuvent être réarrangées, mais peuvent-elles être réarrangées arbitrairement?

Edit 2 : Je continue de chercher une réduction directe, mais voici un croquis du plus proche que j'ai obtenu (ce devrait être une réduction valide, mais a CIRCUIT SAT comme intermédiaire clair; il est quelque peu subjectif que ce soit mieux que composition de deux réductions, comme mentionné au premier paragraphe).

Étant donné , nous savons que peut être de couleur avec sommets tous colorés True si sf a une -clique. Nous les sommets originaux de , puis ajoutons à sommets supplémentaires: avec , . L'invariant clé sera que peut être coloré True si et seulement si parmi les sommets il y a au moins sommets colorés True. Ainsi, chaque peut être vrai. Ensuite, $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$ $C_{ij}$ $\{v_1,\ldots, v_i\}$ $j$ $C_{i0}$ $C_{ij}$ pour obtient la couleur où toutes les couleurs non vraies sont traitées comme fausses. Il existe une -clique dans ssi peut être coloré Vrai, donc si nous forçons cette coloration, le nouveau graphique est colorable ssi il y avait une -clique dans le graphique d'origine. $j > 0$ $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ $k$ $G$ $C_{nk}$ $k$

Les gadgets ET et OU pour appliquer les relations ressemblent beaucoup à la réduction de CIRCUIT SAT à 3 COULEURS, mais ici nous incluons un dans notre graphique, sélectionnons les sommets T, F et Ground, puis connecter tous les autres à tout sauf aux s; cela garantit que les et les autres gadgets ne reçoivent que 3 couleurs. $K_{n-k+1}$ $v_i$ $C_{ij}$

Quoi qu'il en soit, la partie de cette réduction semble directe, mais l'utilisation des portes AND / OR est beaucoup moins directe. La question demeure, y a-t-il une réduction plus élégante? $\overline G$

Edit 3 : Il y a eu quelques commentaires sur les raisons pour lesquelles cette réduction serait difficile à trouver. CLIQUE et k-Color sont en effet des problèmes bien différents. Même sans réduction, cependant, une réponse qui détaille pourquoi la réduction est difficile dans un sens mais possible dans l'autre serait très utile et contribuerait beaucoup au problème.

cc.complexity-theory graph-theory np-hardness reductions William Macrae
la source

Le type de réduction directe que vous recherchez peut être difficile à trouver car la clique et la coloration sont un peu opposées dans le sens où une 1-clique est aussi facile à trouver qu'une n-coloration. Alors peut-être que la réduction devrait être de la forme: a un -coloring si et seulement si a un -clique

G^{'}

$G'$

n - k

$n-k$

G

$G$

k

$k$

Martin Vatshelle

Je conviens que c'est difficile; c'est la raison de mon intérêt; Je vais donner des détails sur la motivation dans la question. Le -coloration idée a me obtenu le plus proche. S'il y a une -clique dans alors peut avoir tous les sommets de la clique monochromatique car ils sont un ensemble indépendant. Le problème est que le nombre chromatique du reste peut varier. Lier deux sommets à un oblige à avoir la même couleur, mais je n'ai aucune idée de quel ensemble de sommets forcer. Un gadget qui force certains des sommets à être monochromes le ferait.

n - k

$n-k$

k

$k$

G

$G$

\bar{G}

$\overline{G}$

K_{n - k - 1}

$K_{n-k-1}$

i

$i$

j

$j$

William Macrae

Je suis d'accord avec Martin ici que cela pourrait même ne pas être faisable (sans passer par, disons 3SAT). La clique et la coloration ont très peu en commun. Je veux donc rappeler le théorème d'Erdős, étant donné les valeurs naturelles g et k, il y a un graphique avec la circonférence au moins g et le nombre chromatique au moins k (pensez-y un moment si vous ne le connaissez pas). Enfin, votre réduction doit également être consciente que si Clique (et ensemble indépendant) est paramétré dans par ensemble de solutions, il n'y a pas de paramétrage équivalent pour le nombre chromatique d'un graphe.

W [1]

$W[1]$

Pål GD

Je ne comprends pas le commentaire de @ MartinVatshelle. Pour autant que je sache, toutes les 1-clique, 1-coloration, n-clique et n-coloration sont triviales au même niveau. (ne pensez pas que vous pouvez toujours répondre à la 1-clique par OUI: le graphique d'entrée peut être vide!)

Yixin Cao

Je pense que le point de Martin est que c'est show et , mais plus difficile de trouver un qu'un . Il y a donc un peu de dualité entre les deux concepts. @ Le point de PålGD sur le théorème d'Erdős est grand (et j'adore ce théorème), car les graphiques avec une grande circonférence ont un grand nombre d'indépendance, et donc leurs inverses auront de grandes cliques. Dans l' ensemble , il se sent comme il y a un piège ici mais, ce qui est de relier cliques et coloriages dans les graphiques identiques ou similaires, mais comme le sens inverse de la réduction pourrait construire un graphique très différent de .

χ (G) = 4

$\chi(G)=4$

χ (G) = 3

$\chi(G)=3$

K_{4}

$K_4$

K_{3}

$K_3$

G

$G$

William Macrae

Réponses:

Etant donné un graphe et un nombre tel que vous voulez savoir si contient un -clique, soit n le nombre de sommets dans . Nous construisons un autre graphe , tel que est -colorable si et seulement si a une -clique, comme suit: $G$ $k$ $G$ $k$ $G$ $H$ $H$ $n$ $G$ $k$

(1) Pour chaque sommet dans , faire une -clique de sommets dans , où varie de à . $v$ $G$ $n$ $(v,i)$ $H$ $i$ $1$ $n$

(2) Ajouter un sommet supplémentaires à . $x$ $H$

$\{x,y,z\}$ $H$ $y=(v,i)$ $z=(u,j)$ $u\ne v$ $i=j$ $u$ $v$ $G$ $\max(i,j)\le k$ $n$ $H$ . Dans cette clique, sélectionnez trois sommets , et . Reliez à chaque sommet de la clique à l'exception de et ; connectez à chaque sommet de la clique à l'exception de et ; et connectez à chaque sommet de la clique à l'exception de et . $x'$ $y'$ $z'$ $x$ $y'$ $z'$ $y$ $x'$ $z'$ $z$ $x'$ $y'$

Les gadgets ajoutés dans l' étape (3) empêchent le triple de sommets , et de l' ensemble étant donné la même couleur que l'autre dans une coloration valide de . La clique dans peut être récupérée à partir d'une coloration de comme l'ensemble des sommets qui sont dans la même classe de couleur que et qui ont . $x$ $y$ $z$ $H$ $G$ $H$ $(v,i)$ $x$ $i\le k$

David Eppstein
la source

C'est magnifique.

William Macrae

Pour une raison quelconque, mon montage a été rejeté, mais la dernière phrase devrait décrire les sommets de G plutôt que H (car elle est destinée à décrire une clique en G). Quelque chose comme "La clique dans

peut être récupérée à partir d'une coloration de H comme

" Aussi, j'ai oublié de dire merci pour la réponse, ça a été très utile!

G

$G$

{v : \exists i \leq k χ ((v, i)) = χ (x)} .

$\{v : \exists i \le k \chi((v,i)) = \chi(x) \}.$

William Macrae

Bien sûr, vous pouvez ajouter une autre clause à cette phrase sur le retrait du

de chaque paire, mais je pensais que cette étape était assez facile à omettre, et mon sentiment général est que (quand elle peut être assez courte) la prose a tendance à être plus lisible qu'une formule.

i

$i$

David Eppstein

Je suis d'accord que la prose est plus préférable. Peut-être que l'ajout d'une phrase comme "la première coordonnée de chaque (v, i) ..." est une idée. La raison de ma préoccupation concernant la technicité est que lors de la première lecture des réductions, il peut être difficile de garder les définitions exactes des éléments dans la première langue et la seconde, et qui est laquelle. La minute où quelque chose semble rompre une définition, cela peut me jeter pour une boucle. Si j'avais du mal à comprendre les phrases précédentes et à arriver à la dernière, je déterminerais que G et H ont des sommets de la forme (v, i).

William Macrae

Je dois également dire que je pense que vous avez fait un bien meilleur travail en parlant de cette réduction que presque tout autre que j'ai lu. Il y a un problème dans la littérature que de nombreuses réductions sont déclarées officiellement sans motivation ni intuition, et vous l'avez très bien évité.

William Macrae

-7

?? la coloration et la découverte de cliques sont connues pour être étroitement couplées depuis des décennies via la théorie des graphes (peut-être même dans les années 60?), même pas via SAT en tant qu'intermédiaire (qui est devenu typique après la preuve Cook en 1971). croient qu'il existe des algorithmes basés sur la propriété de base suivante :

Si G contient une clique de taille k, alors au moins k couleurs sont nécessaires pour colorer cette clique; en d'autres termes, le nombre chromatique est au moins le nombre de clique: $\chi(G) \ge \omega(G).\,$

Je ne suis pas sûr des références exactes mais [1,2] sont de bons points de départ, un algorithme ou une référence exacte est au moins probablement cité dans ces livres.

[1] Cliques, coloration et satisfiabilité, 2ème challenge DIMACS

[2] Dimacs vol 26: Cliques, coloration et satisfiabilité

vzn
la source

En utilisant la propriété

, vous pouvez invoquer un algorithme pour

sur

: si l'algorithme renvoie

, alors

ne contient aucun clique de taille au moins

. Cependant, l'implication opposée ne tient pas: si l'algorithme renvoie

, alors

peut ou non avoir une clique de taille au moins

χ (G) \geq ω (G)

$\chi(G) \geq \omega(G)$

k - C O L O R A B I L I T Y

$k-COLORABILITY$

G

$G$

Y E S

$YES$

G

$G$

k + 1

$k+1$

N O

$NO$

G

$G$

(comme contre-exemple, considérons une pyramide dont la base polygonale a un nombre impair de sommets: elle n'est pas

-colorable, mais elle n'a pas de clique de taille au moins

k + 1

$k+1$

3

$3$

4

$4$

Giorgio Camerani

oui, d'accord; tel que je l'interprète, le message original n'insistait pas sur le sens de la réduction mais mettait davantage l'accent sur le fait d'éviter le SAT en tant qu'intermédiaire, demandant une "explication assez brève". aussi manifestement personne n'a mentionné le factoïde ci-dessus jusqu'à présent .... la question et les commentaires semblent également indiquer de manière inexacte de diverses manières que les deux problèmes ne sont pas étroitement liés ....

vzn

Toutes mes excuses si la direction était ambiguë. Je souhaite une réduction correcte (OUI

⟺

$\iff$ OUI), et je suis intéressé par une réduction de Clique à k-Color. J'ai l'autre sens et c'est expliqué dans mon post. Il y a certainement beaucoup de choses qui relient les cliques dans les graphiques aux colorations dans les graphiques et vice versa, et en effet j'en ai vu beaucoup (et je suppose que beaucoup d'autres ici en ont vu beaucoup), mais je suis vraiment intéressé exclusivement par un direct réduction ou une explication convaincante de la raison pour laquelle il pourrait ne pas exister.

William Macrae

@vzn: Mon commentaire ne visait pas à critiquer votre réponse. À vrai dire, au départ, j'ai fait un raisonnement similaire au vôtre, mais je me suis ensuite rendu compte que, si l'implication opposée avait eu lieu, alors

sur les graphiques généraux, qui est connu pour être NP-complet , aurait pu être résolu trivialement en vérifiant simplement si le graphe d'entrée avait une clique de

nœuds: tout

aurait été à

couleurs si et seulement s'il ne contenait aucune clique de taille

(c'est tout à fait faux, bien sûr, comme le contre-exemple de la pyramide le montre). Au fait: ce n'est pas moi qui ai voté.

3 - C O L O R I N G

$3-COLORING$

4

$4$

G

$G$

3

$3$

4

$4$

Giorgio Camerani

⟺

$\Longleftrightarrow$

C L I Q U E

$CLIQUE$

C O L O R I N G

$COLORING$