Modułowy rozkład i szerokość kliki

Próbuję zrozumieć niektóre pojęcia dotyczące rozkładu modułowego i wykresów szerokości kliki .

W tym artykule („Na wykresach uporządkowanych za pomocą P4”) znajduje się dowód na to, jak rozwiązać problemy z optymalizacją, takie jak liczba kliki lub liczba chromatyczna za pomocą rozkładu modułowego. Rozwiązanie tych problemów przez skomponowanie (przy użyciu sumy rozłącznej lub unii rozłącznej) dwóch wykresów G1, G2 jest łatwe, gdy znasz odpowiedź na G1 i G2. Ponieważ wykresy podstawowe przy rozkładzie grafów uporządkowanych za pomocą P4 są wykresami ograniczonymi (tj. C5, P5 itp.), Łatwo jest je rozwiązać dla tych „przypadków bazowych”, a następnie rozwiązać dla kompozycji. Dlatego przy użyciu drzewa rozkładu możliwe jest rozwiązanie tych problemów w czasie liniowym.

Wygląda jednak na to, że ta technika działałaby z dowolną klasą grafu, tak że liczby pierwsze wykresu są ograniczone. Potem znalazłem ten artykuł „Problemy optymalizacji czasu liniowego na wykresach ograniczonej kliki”, który wydaje się czynić uogólnienie, którego szukałem, ale nie mogłem go dobrze zrozumieć.

Moje pytanie brzmi:

1- Czy równoznaczne jest stwierdzenie, że wykresy podstawowe drzewa rozkładu są ograniczone (jak w przypadku grafów uporządkowanych w P4) i powiedzieć, że wykres ma ograniczoną właściwość „Szerokość kliki”?

2- W przypadku, gdy odpowiedź na 1 brzmi NIE, wówczas: Czy istnieje jakikolwiek wynik dotyczący klas wykresów z ograniczeniami liczb pierwszych (jak w przypadku wykresów uporządkowanych za pomocą P4), a zatem problemy z optymalizacją, takie jak liczba kliki rozwiązana w czasie liniowym na wszystkich tych klasach ?

znajdziesz tekst wprowadzający na temat szerokości kliki (w skrócie cwd): Górne granice szerokości kliki wykresów (B. Courcelle i S. Olariu, DAM 101). W tej ankiecie można znaleźć najnowsze wyniki: Ostatnie zmiany na wykresach ograniczonej szerokości kliki (M. Kamiński, V. Lozin, M. Milanic, DAM 157 (12): 2747-2761 (2009))

Cwd jest miarą złożoności opartą na operacjach grafowych, które uogólniają konkatenację słów. Nieskończone zliczalne wykresy mogły mieć ograniczenia cwd. Powiesz, że zestaw (być może nieskończony) grafów (skończony lub policzalny) ograniczył cwd, jeśli istnieje stała k, tak że dowolny wykres w tym zestawie ma cwd co najwyżej k. Na przykład pełne wykresy mają cwd 2, odległościowe wykresy dziedziczne cwd maksymalnie 3, ...

1) Związek między cwd i modular-dec jest następujący: cwd (G) = max {cwd (H) | H liczba pierwsza w rozkładzie modułowym G}. Dlatego można powiedzieć, że cwd uogólnia fakt, że „wykresy główne ograniczyły rozmiar”. Możesz mieć wykresy z pierwotnymi wykresami o nieograniczonym rozmiarze, ale z ograniczonym cwd.

2) jeśli rozmiar pierwszych wykresów jest ograniczony, cwd jest ograniczony. Wyniki w cytowanym artykule mówią, że każdy problem wyrażalny w MSOL można skutecznie rozwiązać w klasach grafów ograniczonego cwd. Ten zestaw problemów obejmuje wiele problemów NP-zupełnych: liczba kliki, liczba stabilna, 3 kolory, ...

Badane są tutaj niektóre algorytmiczne aspekty dekodowania modułowego „Przegląd algorytmicznych aspektów dekompozycji modułowej” (M. Habib i C. Paul, Computer Science Review 4 (1): 41-59 (2010))