Post zaktualizowany 31 sierpnia : dodałem podsumowanie aktualnych odpowiedzi poniżej oryginalnego pytania. Dzięki za wszystkie interesujące odpowiedzi! Oczywiście każdy może nadal publikować wszelkie nowe ustalenia.
Dla których rodzin grafów istnieje algorytm wielomianowy do obliczania liczby chromatycznej ?
Problem można rozwiązać w czasie wielomianowym, gdy (wykresy dwudzielne). Na ogół, gdy χ ( G ) ≥ 3 , obliczenie liczby chromatycznej jest trudne dla NP, ale istnieje wiele rodzin grafów, w których tak nie jest. Na przykład cykle kolorowania i doskonałe wykresy można wykonywać w czasie wielomianowym.
Ponadto dla wielu klas grafów możemy po prostu ocenić odpowiedni wielomian chromatyczny; kilka przykładów w Mathworld .
Przypuszczam, że większość z powyższych jest powszechnie znana. Z przyjemnością dowiedziałbym się, czy istnieją inne (nietrywialne) rodziny grafów, dla których minimalne zabarwienie grafów można rozwiązać w czasie wielomianowym.
W szczególności interesują mnie algorytmy dokładne i deterministyczne, ale mogę wskazać dowolne interesujące algorytmy losowe lub algorytmy aproksymacyjne.
Aktualizacja (31 sierpnia):
Dziękujemy wszystkim za przesłanie ciekawych odpowiedzi. Oto krótkie podsumowanie odpowiedzi i referencji.
Idealne i prawie idealne wykresy
Algorytmy geometryczne i optymalizacja kombinatoryczna (1988), rozdział 9 (Zestawy stabilne na wykresach). Martin Grotschel, Laszlo Lovasz, Alexander Schrijver.
Rozdział 9 książki pokazuje, jak rozwiązać problem kolorowania za pomocą problemu przykrycia minimalnej wagi kliki. Ponieważ opierają się na elipsoidzie, algorytmy te mogą nie być zbyt przydatne w praktyce. Ponadto rozdział zawiera ładną listę referencyjną dla różnych klas idealnych wykresów.
Optymalizacja kombinatoryczna (2003), tom B, sekcja VI Alexander Schrijver.
Ta książka ma trzy rozdziały poświęcone doskonałym wykresom i ich wielomianowej barwie czasu. Przyjrzałem się tylko szybko, ale podstawowe podejście wydaje się takie samo jak w poprzedniej książce.
Charakterystyka wykresów b-perfect (2010). Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek
Wykresy o ograniczonej szerokości drzewa lub szerokości kliki
Zestaw dominujący na krawędziach i kolory na wykresach ze stałą szerokością kliki (2001). Daniel Kobler, Udi Rotics
Algorytmy wymagają tutaj wyrażenia k (algebraicznej formuły do konstruowania wykresu z ograniczoną szerokością kliki) jako parametru. W przypadku niektórych wykresów wyrażenie to można obliczyć w czasie liniowym.
- Jarosław wskazał na metody zliczania zabarwienia na ograniczonych wykresach szerokości drzewa. Zobacz jego odpowiedź poniżej.
Sparametryzowana złożoność kolorowania wierzchołków (2003). Leizhen Cai.
Sparametryzowane problemy kolorystyczne na wykresach akordowych (2006). Dániel Marks.
Wykresy nie zawierające poszczególnych podgrafów
Decydowanie o kkolorowności grafów wolnych od P5 w czasie wielomianowym (2010). Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.
3-kolorowe wykresy wolne od AT w czasie wielomianowym (2010). Juraj Stacho.
Kolorowanki z czworokątami
- Algorytmy kolorowania czworokątów (1999). David Eppstein, Marshall W. Bern, Brad Hutchings.
źródło
Odpowiedzi:
Jak zaobserwujesz, wszystkie idealne wykresy mogą być pokolorowane w czasie wielomianowym, ale myślę, że dowodem są algorytmy elipsoidalne dla programowania liniowego (patrz książka Grötschela, Lovásza i Schrijvera), a nie cokolwiek bezpośredniego i kombinatorycznego. Istnieje wiele różnych klas grafów, które są podklasami idealnych grafów i mają łatwiejsze algorytmy kolorowania; na przykład wykresy akordów można pokolorować zachłannie za pomocą idealnej kolejności eliminacji.
Wszystkie lokalnie połączone wykresy (wykresy, na których każdy wierzchołek ma połączone sąsiedztwo) mogą być trójkolorowe w czasie wielomianowym, gdy istnieje kolorowanie: po prostu rozszerz trójkąt kolorujący o trójkąt.
Wykresy o maksymalnym stopniu trzecim można pokolorować w czasie wielomianowym: łatwo jest sprawdzić, czy są one dwustronne, a jeśli nie, to albo wymagają tylko trzech kolorów, albo mają K4 jako połączony składnik i wymagają czterech kolorów (twierdzenie Brooksa).
Bez trójkątów płaskie wykresy mogą być barwione w czasie wielomianowym z tego samego powodu: są co najwyżej 3-chromatyczne (twierdzenie Grötzscha).
źródło
Wykresy b-perfect pozwalają na indukowane 5 cykli (w przeciwieństwie do wykresów doskonałych) i wykazano, że mają algorytm wielomianowy do kolorowania według Hoàng, Maffray i Mechebbek, Charakterystyka wykresów b-perfect , arXiv: 1004.5306 , 2010.
(Szkoda, że wspaniałe kompendium klas grafów w ISGCI obejmuje tylko płynność, niezależny zbiór i dominację. Nie zawiera informacji o kolorystyce).
źródło
Również dla wykresów ograniczonej szerokości kliki (która jest bardziej ogólna niż szerokość): Kobler i Rotics .
Również szerokość kliki jest trudna do obliczenia, ale istnieje algorytm aproksymacji Ouma i Seymoura, „zbliżający się do szerokości kliki i szerokości gałęzi” (z przybliżeniem wykładniczym).
źródło
Każda rodzina wykresów z ograniczoną szerokością drzewa będzie miała algorytm wielomianowy do obliczania liczby chromatycznej. Gamarnik redukuje problem liczenia kolorów do problemu obliczania marginesów niektórych losowych pól Markowa zdefiniowanych na tym samym wykresie. Wynik jest następujący, ponieważ marginesy MRF na ograniczonych wykresach szerokości drzewa można obliczyć w czasie wielomianowym za pomocą algorytmu drzewa połączeń .
Aktualizacja 8/26 : Oto przykład zmniejszenia liczby marginesów <-> o <->. Wymaga rozpoczęcia od właściwego kolorowania, które można znaleźć w czasie wielomianu dla ograniczonych wykresów szerokości drzewa z wersją algorytmu drzewa maks. Plus. Teraz, aby pomyśleć o tym ... tak naprawdę nie potrzebujesz # zabarwienia dla liczby chromatycznej, tylko jedno właściwe zabarwienie
źródło
Istnieją również wyniki Daniela Marksa dotyczące złożoności problemu liczby chromatycznej na wykresach, które można przekształcić w akord przez co najwyżej k delecji wierzchołków; dla każdego naprawionego k ten problem jest wielomianowy ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).
źródło
Algorytmy kolorowania czworokątów .
M. Bern, D. Eppstein i B. Hutchings.
http: // arXiv: cs.CG/9907030 .
Al Algorytmica 32 (1): 87–94, 2002.
źródło