Referência para dureza NP de 3 cores?

33

Eu tenho uma pergunta histórica.

Estou tentando determinar a referência para o fato de que 3 cores de gráficos (alternativamente, cores para determinado ) são difíceis de NP.k 3kk3

A resposta tentadora é o "artigo original de Karp", mas isso está errado. Aqui está uma varredura: Redutibilidade entre problemas combinatórios, Karp (1972) . Isso prova que o número cromático (entrada: um gráfico. Saída: ) é difícil. Esse é um problema mais difícil, e a redução é diferente da construção padrão do gadget (com 3 cores, True, False e Ground) que implica em dureza de 3 cores.χ(G)

Garey e Johnson, Computadores e intratabilidade , têm capacidade de como [GT4] e se referem a Karp (1972).k

Thore Husfeldt
fonte
Na página 84, Garey e Johnson afirmam que a 3-colorability é NP-completa, citando o artigo de Stockmeyer fornecido na resposta de Yury. No Teorema 4.2, eles também fornecem uma prova mais simples do resultado de Stockmeyer.
Tyson Williams

Respostas:

44

László Lovász , Coberturas e coloração de hipergrafos , Anais da Quarta Conferência Sudeste de Combinatória, Teoria dos Gráficos e Computação, Utilitas Math., Winitas, Mann., 1973, pp. 3--12, provou que o número cromático se reduz a 3 colorabilidade.

Penso que essa é a primeira prova da NP-completude da 3-colourability.

Aqui está o artigo de Lovász; veja também a excelente explicação de Vašek Chvátal para a redução de Lovász.

vb le
fonte
21

Aqui está outro artigo de 1973 que prova que a 3 cores é NP-difícil.

Larry J. Stockmeyer. “A coloração plana 3 é polinomial completa.” ACM SIGACT News, vol. 5, n. 3, 1973.

(Parece que Lovász e Stockmeyer obtiveram seus resultados independentemente.)

Atualização: veja os comentários abaixo.

Yury
fonte
5
Se não me engano, Stockmeyer não provou a dureza NP da 3-Coloring nesse documento. Lá, ele reduz 3-Coloração para Planar 3-Coloração e refere a dureza de 3-Coloração a Karp (1972). Isso está errado, como apontado por Thore Husfeldt.
usar o seguinte comando
2
Entendo. Obrigado user13136! Infelizmente, não tenho acesso a este documento agora. Vi apenas o resumo deste artigo e as referências a ele.
Yury
4
Eu já vi o artigo de Stockmeyer através da biblioteca digital ACM, e inclui uma prova completa da dureza da 3 cores. (. Redução de 3-satisfiability) Assim, parece como se indicação inicial de Yury é correcta depois de tudo, e Stockmeyer e Lovász obtido o resultado independentemente (e utilizando diferentes reduções.)
Thore Husfeldt
3
Ai! Eu não sabia que apenas uma marca de seleção pode ser atribuída. A resposta da Stockmeyer está correta, então cliquei mecanicamente na marca de seleção. O que devo fazer, dividido entre duas versões mutuamente exclusivas da verdade?
Thore Husfeldt
2
Ah, fiquei curioso porque acho o papel de Lovasz bastante bonito. Eu não queria que a depreciar a resposta de Yury nem pensar vb le é muito coração partido sobre isso;)
user13136