Référence pour la dureté NP de 3 couleurs?

J'ai une question historique.

J'essaie de déterminer la référence pour le fait que la possibilité de coloration sur 3 des graphes (ou colourability pour un ) est NP-difficile. $k$ $k\geq 3$

La réponse tentante est «le papier original de Karp», mais c'est faux. Voici une analyse: Réductibilité parmi les problèmes combinatoires, Karp (1972) . Cela prouve que le nombre chromatique (Entrée: un graphe. La sortie: ) est difficile. C'est un problème plus difficile, et la réduction est différente de la construction standard d'un gadget (avec 3 couleurs, True, False et Ground) qui implique une dureté de 3 couleurs. $\chi(G)$

Garey et Johnson, Computers and intractability , ont la colourability comme [GT4] et se réfèrent à Karp (1972). $k$

np-hardness ho.history-overview Thore Husfeldt
la source

À la page 84, Garey et Johnson affirment que la 3-colorabilité est NP-complète en citant le document Stockmeyer fourni dans la réponse de Yury. Dans le théorème 4.2, ils fournissent également une preuve plus simple du résultat de Stockmeyer.

Tyson Williams

Réponses:

László Lovász , Recouvrement et coloration des hypergraphes , Actes de la quatrième conférence du Sud-Est sur la combinatoire, la théorie des graphes et l'informatique, Utilitas Math., Winnipeg, Man., 1973, p. la colorabilité.

Je pense que c'est la première preuve de la NP-complétude de la 3-colorabilité.

Voici le papier de Lovász; voir aussi l'excellente explication de Vašek Chvátal à la réduction de Lovász.

vb le
la source

Voici un autre article de 1973 qui prouve que la 3-colorabilité est NP-difficile.

Larry J. Stockmeyer. «La planabilité à 3 couleurs est complète polynomiale.» ACM SIGACT News, vol. 5, non. 3, 1973.

(Il semble que Lovász et Stockmeyer aient obtenu leurs résultats de manière indépendante.)

Mise à jour: voir les commentaires ci-dessous.

Yury
la source

Si je ne me trompe pas, Stockmeyer n'a pas prouvé la dureté NP du 3-coloriage dans ce papier. Là, il réduit 3-Coloring à 3-Coloring Planar et fait référence à la dureté de 3-Coloring à Karp (1972). C'est faux, comme l'a souligné Thore Husfeldt.

user13136

Je vois. Merci user13136! Malheureusement, je n'ai pas accès à ce document maintenant. Je n'ai vu que le résumé de cet article et des références à celui-ci.

Yury

J'ai maintenant vu le papier de Stockmeyer via la bibliothèque numérique ACM, qui inclut une preuve complète de la dureté de la 3-colorabilité. (Réduction de 3-Satisfiabilité.) Il semble donc que la déclaration initiale de Yury soit correcte, et Stockmeyer et Lovász ont obtenu le résultat indépendamment (et en utilisant différentes réductions).

Thore Husfeldt le

Aie! Je ne savais pas qu'il ne pouvait y avoir qu'une coche. La réponse de Stockmeyer est correcte, alors j'ai mécaniquement cliqué sur la coche. Que dois-je faire, déchiré, car je suis entre deux versions mutuellement exclusives de la vérité?

Thore Husfeldt

Oh, j'étais simplement curieux parce que je trouve le papier de Lovasz assez joli. Je ne voulais pas déprécier la réponse de Yury et je ne pense pas que vb le soit très navré à ce sujet;)

user13136