co jest łatwe dla niewielkich wykluczonych wykresów?

31

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.

ds.algorithms graph-theory graph-minor

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

23

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?

— András Salamon
źródło

1

Ciekawe ... Zastanawiam się, jak wygląda ten trójlistny rozkład dla płaskich wykresów

— Jarosław Bułatow

2

Przydatnym twierdzeniem, które znalazłem, jest to, że właściwość jest wyrażalna w FP + C, jeżeli jest rozstrzygalna w czasie wielomianowym na ograniczonym wykresie tw. Teraz pytanie brzmi - w jaki sposób złożoność problemów decyzyjnych FP + C wiąże się ze złożonością analogicznych problemów liczenia?

— Yaroslav Bulatov

@Yaroslav: Czy mógłbyś podać referencje na ten temat po jego spisaniu? Dzięki.

— gphilip

3

Lol, właściwie tego nie odkryłem, „znalazłem” na stronie 2 „Logiki, wykresów i algorytmów” Grohe

— Jarosław Bułatow

18

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

— Robin Kothari
źródło

5

Mój artykuł arxiv.org/abs/1006.5440 zawiera kilka nowszych wyników na liście klików o niskiej degeneracji, w tym nieco lepszy czas działania

dla listy wszystkich maksymalnych klików.

O (d n 3^{d / 3})

$O(dn3^{d/3})$

— David Eppstein

Nie widzę zależności między małymi zamkniętymi (twoja odpowiedź) a małymi wyłączonymi wykresami (pytanie). Również zestaw wszystkich kompletnych wykresów jest nieznacznie zamknięty, ale nie mają one ograniczonej degeneracji.

— Saeed,

Drobne zamknięte = drobne wyłączone. Wszystkie nietrywialne rodziny małych zamkniętych grafów ograniczyły zwyrodnienie. Powinienem był dodać „niebanalne” do mojego oryginalnego oświadczenia.

— Robin Kothari

Przede wszystkim drobne zamknięte! = Wykluczone drobne (zamiast wykluczone drobne

drobne zamknięte), w przeciwnym razie możesz podać wiele nowych algorytmów aproksymacyjnych i parametryzowanych dla wielu gęstych klas grafów. Co to są nietrywialne pomniejsze zamknięte wykresy? np. wykresy szerokości co najwyżej f (| G |) są trywialne czy nietrywialne? lub klasa gęstych wykresów (które są drobne zamknięte i dobrze uporządkowane quasi), czy trywialne drobne zamknięte czy nietrywialne? Twoja definicja nie jest jasna, a czytelnik nie może zgadnąć, co masz na myśli (a niektóre z twoich definicji są błędne, jak powiedziałem na początku).

\subset

$\subset$

— Saeed,

Mogę ci powiedzieć, co mam na myśli przez niewielką rodzinę zamkniętych grafów.

jest mniejsze od

jeśli

można uzyskać z

poprzez usunięcie krawędzi, usunięcie izolowanych wierzchołków lub kurczenie się krawędzi. Rodzina grafów to zestaw nieukierunkowanych grafów bez etykiety

(zwykle zbiór nieskończony).

jest rodzina drobne zamknięte, jeżeli dla wszystkich

w

, wszystkie nieletnich

są także

. Rodzina nie jest trywialna, jeśli nie jest zbiorem wszystkich wykresów. Wykresy szerokości

(dla stałej

) są nieznacznie zamknięte, ale wykresy szerokości

H

$H$

G

$G$

H

$H$

G

$G$

F

$F$

F

$F$

G

$G$

F

$F$

G

$G$

F

$F$

k

$k$

k

$k$

zasadniczo nie są nieznacznie zamknięte. Tak to rozumiem. Oczywiście mogę się mylić.

f (| G |)

$f(|G|)$

— Robin Kothari,

15

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 algorytmu czasu, aby znaleźć separator rozmiaru . $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.

— Hsien-Chih Chang 張顯之
źródło

jakiś pomysł, czy separatory pomagają w policzeniu liczby odpowiednich kolorów?

— Yaroslav Bulatov

1

nie bardzo, może papier wspomniany przez Iana pomaga lepiej. Rozszerzenie wyniku znajduje się w „Algorytmach aproksymacji poprzez dekompozycję skurczu” tych samych autorów w SODA '07.

— Hsien-Chih Chang 張顯之

15

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

— Ian
źródło

Dzięki, to dość fascynujące ... Znalazłem bardziej dostępny opis algorytmu rozkładu w „Logice, wykresach i algorytmach” Grohe

— Jarosław Bułatow

0

$K_5$ $K_{3,3}$

$H$ $H$

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

— Rupei Xu
źródło