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

23

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 ?χ(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.χ(G)=2χ(G)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

Wykresy nie zawierające poszczególnych podgrafów

Kolorowanki z czworokątami

Joel Rybicki
źródło
1
Wykresy porównawcze. Jest to prawdopodobnie jedna z trywialnych rodzin, ale nadal uważam, że należy o nich wspomnieć, dlatego używam komentarza zamiast odpowiedzi.
Radu GRIGore
Czy chodziło Ci o wykresy porównywalności, czy też wykresy porównawcze to inna klasa?
Joel Rybicki
Miałem na myśli wykresy porównywalności, które są idealne.
Radu GRIGore
Zauważ, że wykresy B-Perfect są „bliskie” byciu idealnymi, ale nie są do końca takie, ponieważ mogą zawierać 5 cykli.
András Salamon
Twój link do artykułu Cai jest nieprawidłowy.
Jeremy Kun

Odpowiedzi:

14

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

David Eppstein
źródło
8

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

András Salamon
źródło
Odnośnie ISGCI: Jeśli niezależne zestawy są łatwe, może to oznaczać , że kolorowanie również może być łatwe. Dlatego przeglądanie ISGCI może dać nowe pomysły na dalsze google.
Jukka Suomela
Co więcej, wiele artykułów cytowanych w ISGCI rozważa zabarwienie, a także ZESTAW KLIKNIĘTY / NIEZALEŻNY. Ale istnieje ponad 1000 odniesień do przebrnięcia przez ...
András Salamon
Dzięki. ISGCI wygląda obiecująco, więc może tam przejdę.
Joel Rybicki
8

Również dla wykresów ograniczonej szerokości kliki (która jest bardziej ogólna niż szerokość): Kobler i Rotics .

nf(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

Magnus Wahlström
źródło
8

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

Jarosław Bułatow
źródło
6

P5C5P5

2P3

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

Bart Jansen
źródło
Dzięki! Odniesienia te wydają się dość interesujące (w szczególności artykuł „Decydowanie o k-zabarwieniu grafów wolnych od P5 w wielomianu).
Joel Rybicki
4

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.

Aryabhata
źródło