Algorytmy przestrzeni logów na wykresach z ograniczoną szerokością drzewa

Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Trudno jest obliczyć szerokość drzewa. Najbardziej znany algorytm aproksymacyjny osiąga współczynnik . $O(\sqrt{{\log}n})$

Twierdzenie Courcelle'a stwierdza, że dowolną właściwość grafów definiowalną w monadycznej logice drugiego rzędu (MSO2) można rozstrzygać w czasie liniowym na dowolnej klasie wykresów o ograniczonej szerokości drzewa . Niedawny artykuł wykazał, że twierdzenie Courcelle'a nadal obowiązuje, gdy „czas liniowy” zostaje zastąpiony przez „logspace”. Nie rozwiązuje to jednak złożoności przestrzennej izomorfizmu grafów na wykresach o ograniczonej szerokości drzewa. Najbardziej znany wynik umieszcza go w LogCFL.

Czy istnieją inne problemy, które:

NP-twardy (lub nieznany jako P) na ogólnych wykresach, oraz
znany z możliwości rozwiązania w czasie liniowym / wielomianowym na wykresach z ograniczoną szerokością drzewa, oraz
NIE wiadomo, że jest w LogSpace?

cc.complexity-theory ds.algorithms graph-theory space-bounded treewidth Shiva Kintali
źródło

Jaka jest wymieniona we współczynniku aproksymacji?

n

$n$

gphilip

n

$n$ jest liczbą wierzchołków na wykresie wejściowym.

Shiva Kintali,

Zasadniczo możemy lepiej niż w przybliżeniu szerokości. Najlepszy znany mi algorytm aproksymacji czasu wielomianowego osiąga współczynnik aproksymacji , gdzie jest szerokością wykresu. Patrz Feige, Hajiaghayi i Lee, Ulepszone algorytmy aproksymacyjne dla separatorów wierzchołków o minimalnej masie , STOC 2005.

O (\sqrt{\log n})

$O(\sqrt{\log n})$

O (\sqrt{\log w})

$O(\sqrt{\log w})$

w

$w$

gphilip

Odpowiedzi:

Przykładem jest wielomian Tutte .

Jest to uogólnienie wielomianu chromatycznego , który sam w sobie jest trudnym problemem # P w każdej rozsądnej formulacji. W

Ocena wielomianu Tutte dla wykresów ograniczonej szerokości drzewa , SD Noble, kombinatoryka, prawdopodobieństwo i obliczenia, 1998,

$O(f(k)n^{4+\epsilon})$ $k$ $n$

Wygląda na to, że problemu nie da się wyrazić bezpośrednio w MSO2, chociaż nie znam szczegółowych definicji ... Mam nadzieję, że ten problem jest tym, czego potrzebujesz!

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

Jaka jest funkcja f?

Michael Blondin,

k

$k$

O (2^{(k^{3 + ϵ})})

$O(2^{(k^{3+\epsilon})})$

Makowski mówi, że „wszystkie wielomiany grafów badane w literaturze są definiowalne przez SOL”, i podaje sformułowanie wielomianu Tutte pod względem SOL, strona 15 w „Od zoo do zoologii: w kierunku ogólnej teorii wielomianów grafowych”. W „Algorytmicznych zastosowaniach twierdzenia Fefermana-Vaught'a” rozszerza twierdzenie Courcelle'a, aby pokazać wykonalność wielomianów definiowanych przez SOL na ograniczonych grafach szerokości drzewa.

Yaroslav Bulatov