co jest łatwe dla niewielkich wykluczonych wykresów?

Przybliżenie liczby kolorów wydaje się łatwe na niewielkich wykluczonych wykresach przy użyciu algorytmu Jung / Shah. Jakie są inne przykłady problemów, które są trudne na ogólnych wykresach, ale łatwe na niewielkich wykluczonych wykresach?

Aktualizacja 10/24 Wydaje się, że podąża za wynikami Grohe, że wzór, którym jest FPT do testowania na wykresach ograniczonej szerokości, to FPT do testowania na niewielkich wykluczonych wykresach. Teraz pytanie brzmi - w jaki sposób odnosi się to do wykonalności liczenia satysfakcjonujących zadań takiej formuły?

Powyższe stwierdzenie jest fałszywe. MSOL jest FPT na ograniczonych wykresach szerokości drzewa, jednak trójkolorowość jest NP-kompletna na płaskich wykresach, które są pomijane.

Najbardziej ogólny znany wynik to Grohe. Podsumowanie zostało przedstawione w lipcu 2010 r .:

• Martin Grohe, Definicja punktu stałego i czas wielomianowy na wykresach z małymi wykluczonymi , LICS 2010. ( PDF )

Krótko mówiąc, każde wyrażenie, które można wyrazić w logice stałoprzecinkowej z liczeniem, ma algorytm czasu wielomianowego na klasach wykresów z co najmniej jednym wykluczonym pomniejszeniem. (FP + C to logika pierwszego rzędu wzbogacona o operator stałoprzecinkowy i predykat, który daje liczność definiowalnych zestawów wierzchołków). Kluczową ideą jest to, że wykluczenie pomniejszenia pozwala grafom w klasie na uporządkowanie treelike rozkładów, które można zdefiniować w logice stałoprzecinkowej (bez liczenia).

Tak więc dużą liczbę odpowiedzi na twoje pytanie można uzyskać, biorąc pod uwagę właściwości, które można zdefiniować w FP + C, ale które trudno policzyć.

Edycja: Nie jestem pewien, czy to faktycznie odpowiada na twoje pytanie, tym bardziej w przypadku twojej aktualizacji. Wskaźnik i stwierdzenie wyniku Grohe są poprawne, ale nie sądzę, że przekreślony tekst jest odpowiedni dla twojego pytania. (Podziękowania dla Stephana Kreutzera za zwrócenie na to uwagi.) Być może warto wyjaśnić: czy chcesz mieć problem z liczeniem, który jest ogólnie trudny, ale łatwy w przypadku klas wykluczonych z lekcji, czy problem decyzyjny?

Ciekawą właściwością niewielkich zamkniętych rodzin grafów jest to, że ograniczyły degenerację . Oznacza to, że wszystkie problemy, które są łatwe na wykresach związanych ze zwyrodnieniem, są łatwe na wykresach z niewielkiej, zamkniętej rodziny.

Na przykład sprawdzenie, czy wykres zawiera klikę o rozmiarze k, jest zwykle trudnym problemem, a najlepsze algorytmy to . Jeśli jednak wiemy, że degeneracja jest stała, wówczas k-kliki można znaleźć w czasie liniowym, tj. W czasie O (n). Artykuł Wikipedii na temat problemu kliki zawiera również informacje na ten temat. (Dokładny czas działania jest podobny do O ( k d ( G ) k n ) .) Ten algorytm opracowali Chiba i Nishizeki .$O(n^k)$$O(k d(G)^k n)$

Inne przykłady można znaleźć w tej odpowiedzi Davida Eppsteina z MathOverflow na podobne pytanie dotyczące wykresów z ograniczoną degeneracją.

Jako uzupełnienie, kolejną przydatną właściwością algorytmów na wykresach z niewielkimi wykluczeniami jest to, że wykresy te mają małe separatory . Dokładniej, z powodu

Algorytm czasu liniowego do znalezienia separatora na wykresie z wyłączeniem pomniejszej , Bruce Reed i David R. Wood, ACM Transactions on Algorytmy, 2009,

jest liniowy algorytm czas znaleźć separator rozmiaru , lub O ( n 3 / 2 + m ) algorytmu czasu, aby znaleźć separator rozmiaru O ( n 1 / 2 ) .$O(n^{2/3})$$O(n^{3/2} + m)$$O(n^{1/2})$

Separatory są dobre dla technik programowania dynamicznego , a wiele problemów z kompletnym NP ma szybkie algorytmy z dobrym współczynnikiem aproksymacji, powiedzmy, że rozwiązanie mieści się w stałym współczynniku optymalnym, a nawet PTAS. Wykresy płaskie i ogólnie wykresy z ograniczonymi rodzajami są dobrym punktem wyjścia przy próbach rozwiązania problemów na niewielkich wykluczonych wykresach.

$O(1)$

Drobna teoria wykresów algorytmicznych: rozkład, aproksymacja i kolorowanie według Demaine'a, Hajiaghayi i Kawarabayashi

W tym artykule przedstawiono algorytmiczną wersję pewnego (nieco złożonego do wyjaśnienia) rozkładu dla grafów wyłączonych-mniejszych gwarantowanych przez twierdzenie Robertsona i Seymour'a, co daje szereg poprawionych wyników aproksymacji. Sprawdź także zawarte w nim odniesienia.

$K_5$$K_{3,3}$

$H$$H$

$K_t$$(t-1)$$K_t$$(t-1)$$t− 2$