Rodziny wykresów z wielomianowymi algorytmami czasowymi do obliczania liczby chromatycznej

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

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.$\chi(G) = 2$$\chi(G) \ge 3$

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.

$k$

• Sparametryzowana złożoność kolorowania wierzchołków (2003). Leizhen Cai.

  $k$$k$

• Sparametryzowane problemy kolorystyczne na wykresach akordowych (2006). Dániel Marks.

  $k$$k$

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.

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).

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ównież dla wykresów ograniczonej szerokości kliki (która jest bardziej ogólna niż szerokość): Kobler i Rotics .

$n^{f(k)}$

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).

$k$

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

$P_5$$C_5$$P_5$

$2P_3$

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 ).

Algorytmy kolorowania czworokątów .
M. Bern, D. Eppstein i B. Hutchings.
http: // arXiv: cs.CG/9907030 .
Al Algorytmica 32 (1): 87–94, 2002.

Rozważamy kilka odmian problemu kolorowania kwadratów kwadratu, aby żadne dwa sąsiednie kwadraty nie były jednakowo kolorowe. Podajemy proste liniowe algorytmy czasowe dla trójwymiarowych zrównoważonych czworoboków z przyleganiem do krawędzi, czterokolorowych niezrównoważonych czworoboków z przyleganiem do krawędzi oraz sześciokolorowych zrównoważonych lub niezrównoważonych czworoboków z przyleganiem do narożników. Liczba kolorów używanych przez dwa pierwsze algorytmy jest optymalna; w przypadku trzeciego algorytmu czasami może być potrzebnych 5 kolorów.