Odniesienie do twardości NP 3-zabarwienia?

33

Mam pytanie historyczne.

Próbuję ustalić odniesienie dla faktu, że 3-kolorowalność grafów (alternatywnie, kolorowalność dla danego k 3 ) jest NP-trudna.kk3

Kuszącą odpowiedzią jest „oryginał Karpa”, ale to nieprawda. Oto skan: Reducibility Among Combinatorial Problems, Karp (1972) . Dowodzi to, że liczba chromatyczna (Wejście: wykres. Wyjście: ) jest trudne. To trudniejszy problem, a redukcja różni się od standardowej konstrukcji gadżetu (z 3 kolorami, True, False i Ground), co oznacza twardość 3-kolorowalności.χ(G)

Garey i Johnson, Computers and inctractability , mają kolorowalność jako [GT4] i odnoszą się do Karp (1972).k

Thore Husfeldt
źródło
Na stronie 84 Garey i Johnson twierdzą, że trójkolorowość jest kompletna z NP, powołując się na papier Stockmeyer podany w odpowiedzi Yury. W Twierdzeniu 4.2 stanowią one również prostszy dowód wyniku Stockmeyera.
Tyson Williams

Odpowiedzi:

44

László Lovász , Pokrycia i zabarwienie hipergraphów , Materiały z IV Konferencji Południowo-Wschodniej na temat kombinatoryki, Teorii Grafów i Informatyki, Utilitas Math., Winnipeg, Man., 1973, s. 3--12, udowodniły, że liczba Chromatyczna zmniejsza się do 3 kolorowalność.

Myślę, że to pierwszy dowód na kompletność NP 3-kolorowalności.

Oto praca Lovásza; zobacz także doskonałe wyjaśnienie Vaška Chvátala na temat obniżki Lovásza.

vb le
źródło
21

Oto kolejny papier z 1973 r., Który dowodzi, że 3-kolorowalność jest trudna do NP.

Larry J. Stockmeyer. „Planarna 3-kolorowalność jest zakończona wielomianem.” ACM SIGACT News, vol. 5, nr 3, 1973.

(Wygląda na to, że Lovász i Stockmeyer uzyskali swoje wyniki niezależnie).

Aktualizacja: patrz komentarze poniżej.

Jurij
źródło
5
Jeśli się nie mylę, Stockmeyer nie udowodnił w tym dokumencie twardości NP 3-zabarwienia. Tam redukuje 3-zabarwienie do 3-płaskiego zabarwienia i odnosi twardość 3-zabarwienia do Karp (1972). Jest to błędne, jak zauważył Thore Husfeldt.
user13136 27.04.13
2
Widzę. Dzięki użytkownik13136! Niestety nie mam teraz dostępu do tego artykułu. Widziałem tylko streszczenie tego artykułu i odniesienia do niego.
Yury
4
Widziałem teraz papier Stockmeyera za pośrednictwem biblioteki cyfrowej ACM i zawiera on pełny dowód twardości trójkolorowości. (Zmniejszenie z 3-satysfakcji.) Wydaje się więc, że początkowe stwierdzenie Yury jest jednak poprawne, a Stockmeyer i Lovász uzyskali wynik niezależnie (i stosując różne obniżki.)
Thore Husfeldt
3
Ojej! Nie wiedziałem, że można przypisać tylko jeden znacznik wyboru. Odpowiedź Stockmeyera jest prawidłowa, więc mechanicznie kliknąłem znacznik wyboru. Co powinienem zrobić rozdarty między dwiema wykluczającymi się wersjami prawdy?
Thore Husfeldt
2
Och, byłem po prostu ciekawy, ponieważ uważam, że gazeta Lovasz jest całkiem ładna. Nie chciałem umniejszać odpowiedzi Yury, ani nie sądzę, że VB le jest bardzo
załamany