Odniesienie do twardości NP 3-zabarwienia?

Mam pytanie historyczne.

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

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. $\chi(G)$

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

np-hardness ho.history-overview

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

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

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

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

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

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

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

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