Właściwości MSO, wykresy płaskie i niewielkie wykresy

11

Twierdzenie Courcelle'a stwierdza, że ​​każdą właściwość grafu definiowaną w monadycznej logice drugiego rzędu można rozstrzygać w czasie liniowym na wykresach ograniczonej szerokości . Jest to jedno z najbardziej znanych algorytmicznych meta-twierdzeń.

Zmotywowany twierdzeniem Courcelle, wysunąłem następujące przypuszczenie:

Przypuszczenie : Niech będzie dowolną właściwością definiowaną przez MSO. Jeśli ψ można rozwiązać w czasie wielomianowym na grafach płaskich, to ψ można rozwiązać w czasie wielomianowym na wszystkich klasach mniej istotnych grafów.ψψψ

Chcę wiedzieć, czy powyższa hipoteza jest oczywiście fałszywa, tj. Czy istnieje właściwość definiowana przez MSO, która jest rozwiązywalna w czasie wielomianowym na grafach płaskich, ale trudna NP na pewnej klasie grafów wolnych od drobnych?

Taka jest motywacja mojego wcześniejszego pytania : czy są jakieś problemy, które można rozwiązać wielomianowo na wykresach rodzaju g, ale NP-trudne na wykresach rodzaju> g.

Shiva Kintali
źródło

Odpowiedzi:

18

Masz 4 kolory? Z pewnością MSO i trywialne na wykresach płaskich. Jest NP-kompletny dla wystarczająco dużej niedozwolonej kliki mniejszej, poprzez redukcję do płaskiej 3-kolorowalności.

mikrofon
źródło
1
Mówiąc dokładniej, 4-kolorowalność jest kompletna dla NP w niewielkiej, zamkniętej rodzinie grafów wierzchołkowych, poprzez redukcję do płaskiej 3-kolorowalności.
David Eppstein,