Problemy z optymalizacją MSOL na wykresach ograniczonej płynności z predykatami liczności

CMSOL to zliczanie logiki monadycznej drugiego rzędu, tj. Logiki grafów, w których domeną jest zestaw wierzchołków i krawędzi, istnieją predykaty dla przylegania wierzchołków i wierzchołków oraz występowania krawędzi i wierzchołków, istnieje kwantyfikacja na krawędziach, wierzchołkach, zestawach krawędzi i wierzchołkach ustawia, a istnieje predykat która wyraża, czy rozmiar jest modulo . $\textrm{Card}_{n,p}(S)$ $S$ $n$ $p$

Słynne twierdzenie Courcelle'a stwierdza, że jeśli jest właściwością grafów wyrażalnych w CMSOL, to dla każdego wykresu szerokości co najwyżej można zadecydować w czasie liniowym, czy utrzymuje się, pod warunkiem, że na wejściu podany jest rozkład drzewa Późniejsze wersje tego twierdzenia porzuciły wymóg podania dekompozycji drzewa na wejściu (ponieważ można go obliczyć za pomocą algorytmu Bodlaendera ), a także umożliwiły optymalizację zamiast jedynie decyzji; tzn. biorąc pod uwagę wzór MSOL , możemy również obliczyć największy lub najmniejszy zbiór który spełnia $\Pi$ $G$ $k$ $\Pi$ $G$ $\phi(S)$ $S$ . $\phi(S)$

Moje pytanie dotyczy dostosowania twierdzenia Courcelle'a do wykresów ograniczonej szerokości kliki. Podobne twierdzenie mówi, że jeśli masz MSOL1, który umożliwia kwantyfikację wierzchołków, krawędzi, zestawów wierzchołków, ale nie zestawów krawędzi, wówczas otrzymujesz wykres kliquewidth (z danym wyrażeniem kliki), dla każdego ustalonego można zdecydować w czasie liniowym, czy wykres spełnia pewną formułę MSOL1 ; wszystkie odniesienia, które widziałem, wskazują $G$ $k$ $k$ $G$ $\phi$

Problemy optymalizacji czasu liniowego rozwiązane na wykresach ograniczonej szerokości kliki autorstwa Courcelle, Makowsky and Rotics, Theory of Computing Systems, 2000.

Próbowałem przeczytać artykuł, ale nie jest on samowystarczalny w odniesieniu do dokładnej definicji MSOL1 i jest szczerze trudny do odczytania. Mam dwa pytania dotyczące tego, co dokładnie można zoptymalizować w FPT, sparametryzowane przez płynność wykresu, jeśli na wejściu podano wyrażenie kliki.

Czy MSOL1 zezwala na na testowanie wielkości zbioru modulo jakiejś liczby? $\textrm{Card}_{n,p}(S)$
Czy można znaleźć minimalny / maksymalny zestaw rozmiarów który spełnia wzór MSOL1 $S$ w FPT sparametryzowanej za pomocą skośności, gdy podane jest wyrażenie? $\phi(S)$

W przypadku obu tych pytań chciałbym również wiedzieć, jakie poprawne odniesienia należy przytoczyć, twierdząc, że te wyniki. Z góry dziękuję!

ds.algorithms reference-request graph-algorithms descriptive-complexity cliquewidth Bart Jansen
źródło

Próbowałem zmodyfikować część Twojego artykułu, przepraszam za to. Ponieważ jestem bardzo zainteresowany twoim pytaniem, ale nadal po modyfikacji nie jestem pewien, czy dobrze rozumiem twoje pomysły. Czy masz na myśli, że potrzebujesz dokładnej definicji MSOL1 oraz istnienia predykatu i FPT problemu optymalizacji?

Hsien-Chih Chang 24 之

M S O L_{1}

$MSOL_1$

ϕ (S)

$\phi(S)$

S

$S$

ϕ

$\phi$

_{n, p} (S)

$_{n,p}(S)$

S

$S$

ϕ (S)

$\phi(S)$

f (k) | V (G) |^{O (1)}

$f(k) |V(G)|^{O(1)}$

f

$f$

S

$S$

ϕ

$\phi$

Przydatne mogą być tomy szkicu Brunona Courcelle'a: patrz labri.fr/perso/courcell/ActSci.html w części „Struktura wykresu i monadyczna logika drugiego rzędu, podejście teoretyczne”.

András Salamon

Dzięki; to przynajmniej rozwiązuje część 1) problemu, ponieważ jego Twierdzenie 6.4 w pierwszej części książki mówi: Dla wszystkich zbiorów skończonych K i L etykiet wierzchołków i krawędzi problem sprawdzania modelu formuły Liczenie MSOL1 jest naprawiony parametr sześcienny w odniesieniu do parametru cliquewidth (G) + rozmiar formuły.

Bart Jansen

Odpowiedzi:

Po zadaniu kilku pytań wydaje się, że odpowiedzi na 1) i 2) są TAK. Optymalizacja liczności zbioru jest możliwa w LinEMSOL (jak wspomniał Martin Lackner); jak już powiedziano, istnienie predykatów liczności nie stanowi problemu, ponieważ można je skutecznie obsłużyć przez automaty drzewiaste o skończonym stanie, które powinny podążać (wyraźniej niż w pierwotnie cytowanym dokumencie) z parsowania drzew i Myhill-Nerode- typ narzędzia do obsługi wykresów ograniczonej szerokości rang .

Bart Jansen
źródło

http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf (o którym wspomniałeś, ale lepiej czytelna wersja) definiuje LinEMSOL (definicja 10). LinEMSOL pozwala na problemy z optymalizacją MSO1, a Twierdzenie 4 stwierdza, że takie problemy są możliwe do rozwiązania ze względu na ustalony parametr w odniesieniu do szerokości kliki. Zatem odpowiedź na twój drugi punkt / pytanie powinna brzmieć „tak”.

Odnośnie pierwszego pocisku: W „Wierzchołkach nieletnich, monadycznej logice drugiego rzędu i przypuszczeniu Seese” Bruno Courcelle i Sang-il Oum autorzy piszą, że „Można udowodnić, że żadna formuła stwardnienia rozsianego can (X) nie jest w stanie wyrazić , w każdej strukturze, że zbiór X ma nawet liczność [10] „gdzie [10] =„ Courcelle, Monadyczna logika drugiego rzędu grafów ”

Mam nadzieję, że to pomaga

Martin Lackner
źródło

Dzięki za wgląd, ale fakt, że żadna formuła MS (ogólnie) nie może wyrazić, czy zbiór ma nawet liczność, nie jest tutaj tak naprawdę istotny, ponieważ pytanie dotyczy języka Counting MSOL, który ma specjalne predykaty, które wyraźnie pozwalają na testowanie liczności z zestawu modulo jakaś stała liczba; stąd w języku Counting MSOL możliwe jest wyrażenie równości zbioru, a pytanie brzmiało, czy możemy skutecznie znaleźć najmniejszy / największy zestaw spełniający zdanie w Counting MSOL sparametryzowane przez cliquewidth. W każdym razie dzięki!

Bart Jansen

Masz oczywiście rację. Chciałem tylko podkreślić, że wspomniany artykuł nie obejmuje CMSOL. (Nie znam wyniku, który to robi.)

Martin Lackner