Szerokość kliki - Clique-width

Konstrukcja grafu dziedzicznego odległościowego szerokości kliki 3 przez sumy rozłączne, zmiany etykiet i złączenia etykiet. Etykiety wierzchołków są wyświetlane jako kolory.

W teorii wykres The klika szerokości z wykresu jest parametrem, który opisuje, złożoności strukturalnej wykres; jest ściśle związany z szerokością drzewa , ale w przeciwieństwie do szerokości drzewa może być ograniczany nawet w przypadku gęstych grafów . Definiuje się ją jako minimalną liczbę etykiet potrzebną do skonstruowania za pomocą następujących 4 operacji: ${\ Displaystyle G}$ ${\ Displaystyle G}$

Tworzenie nowego wierzchołka v z etykietą i ( zaznaczono i(v) )
Rozłączne połączenie dwóch oznaczonych grafów G i H (oznaczone ) ${\ Displaystyle G \ oplus H}$
Łączenie krawędzią każdego wierzchołka oznaczonego i z każdym wierzchołkiem oznaczonym j (oznaczonym jako η(i,j) ), gdzie $i\neqj$
Zmiana nazwy etykiety i na etykietę j (oznaczoną jako ρ ( i , j ))

Wykresy ograniczonej szerokości kliki obejmują kografy i wykresy dziedziczne odległości . Chociaż NP-trudno jest obliczyć szerokość kliki, gdy jest ona nieograniczona, i nie wiadomo, czy można ją obliczyć w czasie wielomianowym, gdy jest ona ograniczona, znane są wydajne algorytmy aproksymacji szerokości kliki. W oparciu o te algorytmy i twierdzenie Courcelle'a wiele problemów optymalizacji grafów, które są NP-trudne dla dowolnych grafów, można szybko rozwiązać lub aproksymować na grafach o ograniczonej szerokości kliki.

Sekwencje konstrukcyjne leżące u podstaw koncepcji szerokości kliki sformułowali Courcelle , Engelfriet i Rozenberg w 1990 oraz Wanke (1994) . Nazwa „szerokość kliki” została użyta dla innej koncepcji przez Chlebíkovą (1992) . Do 1993 roku termin ten miał już swoje obecne znaczenie.

Specjalne klasy grafów

Wykresy to dokładnie grafy z szerokością kliki co najwyżej 2. Każdy wykres dziedzicznej odległości ma szerokość co najwyżej 3. Jednak szerokość klik grafów przedziałów jednostkowych jest nieograniczona (na podstawie ich struktury siatki). Podobnie szerokość kliki dwudzielnych grafów permutacji jest nieograniczona (bazuje na podobnej strukturze siatki). W oparciu o charakterystykę wykresów jako grafów bez podwykresu indukowanego, które są izomorficzne z ścieżką bez cięciw o czterech wierzchołkach, sklasyfikowano szerokość klik wielu klas grafów zdefiniowanych przez zakazane podwykresy indukowane.

Inne grafy z ograniczoną szerokością kliki zawierają potęgi $k-$ liści dla ograniczonych wartości $k$ ; są to indukowane podgrafy liści drzewa $T$ w grafie mocy $T k$ . Jednak potęgi liści z nieograniczonymi wykładnikami nie mają ograniczonej szerokości kliki.

Miedza

Courcelle i Olariu (2000) oraz Corneil i Rotics (2005) udowodnili następujące ograniczenia szerokości kliku niektórych grafów:

Jeśli graf ma szerokość kliki co najwyżej $k$ , tak samo ma każdy indukowany podgraf .
Wykres dopełnienie stanowi wykres klika szerokości $k$ ma kliki szerokości co najwyżej $2 k$ .
Wykresy szerokości drzewa $w$ mają szerokość kliki co najwyżej $3 \cdot 2 w - 1$ . Zależność wykładnicza w tym ograniczeniu jest konieczna: istnieją grafy, których szerokość kliki jest wykładniczo większa niż szerokość drzewa. W przeciwnym kierunku grafy o ograniczonej szerokości kliki mogą mieć nieograniczoną szerokość drzewa; na przykład, grafy pełne $n$ -wierzchołków mają szerokość kliki 2, ale szerokość drzewa $n$ $- 1$ . Jednak grafy o szerokości kliki $k$ , które nie mają pełnego dwudzielnego grafu $K$ $t$ $,$ $t$ jako podgraf, mają szerokość drzewa co najwyżej $3$ $k$ $($ $t$ $- 1) - 1$ . Dlatego dla każdej rodziny grafów rzadkich posiadanie ograniczonej szerokości drzewa jest równoważne posiadaniu ograniczonej szerokości kliki.
Inny parametr grafu, ranga-szerokość , jest ograniczony w obu kierunkach przez klikę-szerokość: ranga-width ≤ klika-szerokość ≤ 2 ^{ranga-szerokość + 1} .

Dodatkowo, jeśli graf $G$ ma szerokość kliki $k$ , to potęga grafu $G c$ ma szerokość kliki co najwyżej $2 kc k$ . Chociaż istnieje luka wykładnicza zarówno w ograniczeniu dla szerokości kliki od szerokości drzewa, jak i ograniczeniu dla szerokości klik dla potęg grafu, ograniczenia te nie łączą się ze sobą: jeśli graf $G$ ma szerokość drzewa $w$ , to $G c$ ma szerokość kliki najwyżej $2(c + 1) w + 1 - 2$ , tylko pojedynczo wykładnicza w szerokości drzewa.

Złożoność obliczeniowa

Nierozwiązany problem w matematyce :

Czy grafy ograniczonej szerokości kliki można rozpoznać w czasie wielomianowym?

(więcej nierozwiązanych problemów z matematyki)

Wiele problemów optymalizacyjnych, które są NP-trudne dla bardziej ogólnych klas grafów, można skutecznie rozwiązać za pomocą programowania dynamicznego na grafach o ograniczonej szerokości kliki, gdy znana jest sekwencja konstrukcji dla tych grafów. W szczególności, każda właściwość grafu, która może być wyrażona w monadycznej logice drugiego rzędu MSO ₁ (forma logiki umożliwiająca kwantyfikację na zbiorach wierzchołków) ma algorytm czasu liniowego dla grafów o ograniczonej szerokości kliki, w postaci twierdzenia Courcelle'a .

Możliwe jest również znalezienie optymalnego kolorowania grafu lub cykli hamiltonowskich dla grafów o ograniczonej szerokości klik w czasie wielomianu, gdy znany jest ciąg konstrukcji, ale wykładnik wielomianu rośnie wraz z szerokością kliki, a dowody z teorii złożoności obliczeniowej pokazują że ta zależność będzie prawdopodobnie konieczna. Wykresy ograniczonej szerokości są kliki $\times$ -bounded , co oznacza, że ich liczba chromatyczna jest co najwyżej funkcją wielkości ich największej kliki.

Za pomocą algorytmu opartego na dekompozycji dzielonej można w czasie wielomianowym rozpoznać grafy szerokości kliki trzy i znaleźć dla nich sekwencję konstrukcyjną . W przypadku wykresów o nieograniczonej szerokości klik, NP-trudne jest dokładne obliczenie szerokości klik, a także NP-trudne, aby uzyskać przybliżenie z subliniowym błędem addytywnym. Jednakże, gdy szerokość kliki jest ograniczona, możliwe jest uzyskanie ciągu konstrukcji o ograniczonej szerokości (wykładniczo większej niż rzeczywista szerokość kliki) w czasie wielomianowym. Pozostaje otwarte, czy dokładną szerokość kliki lub ściślejsze jej przybliżenie można obliczyć w czasie praktycznym o stałych parametrach , czy można ją obliczyć w czasie wielomianowym dla każdego ustalonego ograniczenia szerokości kliki, czy nawet wykresy o szerokości kliki cztery można rozpoznać w czasie wielomianowym.

Stosunek do szerokości drzewa

Teoria grafów o ograniczonej szerokości kliki przypomina teorię dla grafów o ograniczonej szerokości drzewa , ale w przeciwieństwie do szerokości drzewa dopuszcza grafy gęste . Jeśli rodzina grafów ma ograniczoną szerokość kliki, to albo ma ona ograniczoną szerokość drzewa, albo każdy kompletny graf dwudzielny jest podgrafem grafu w rodzinie. Szerokość drzewa i szerokość kliki są również połączone przez teorię wykresów liniowych : rodzina grafów ma ograniczoną szerokość drzewa wtedy i tylko wtedy, gdy ich wykresy liniowe mają ograniczoną szerokość kliki.

Uwagi

Bibliografia

Brandstädt, A. ; Dragan, FF; Le, H.-O.; Mosca, R. (2005), „Nowe klasy grafów ograniczonej szerokości kliki”, Teoria systemów obliczeniowych , 38 (5): 623–645, CiteSeerX 10.1.1.3.5994 , doi : 10.1007/s00224-004-1154- 6 , S2CID 2309695.
Brandstädt, A. ; Engelfriet, J.; Le, H.-O.; Lozin, VV (2006), "Clique-width for 4-vertex zabronione subgraphs", Theory of Computing Systems , 39 (4): 561-590, doi : 10.1007/s00224-005-1199-1 , S2CID 20050455.
Brandstädt, Andreas; Hundt, Christian (2008), „Wykresy ptolemejskie i wykresy interwałowe to potęgi liści”, ŁACIŃ 2008: Informatyka teoretyczna , Notatki z wykładu w informatyce. Sci., 4957 , Springer, Berlin, s. 479-491, doi : 10.1007/978-3-540-78773-0_42 , MR 2472761.
Brandstädt, A. ; Lozin, VV (2003), „O strukturze liniowej i szerokości kliki dwudzielnych wykresów permutacji”, Ars Combinatoria , 67 : 273–281, CiteSeerX 10.1.1.16.2000.
Chlebíková, J. (1992), „Na szerokości drzewa wykresu”, Acta Mathematica Universitatis Comenianae , Nowa seria, 61 (2): 225-236, CiteSeerX 10.1.1.30.3900 , MR 1205875.
Cogis, O.; Thierry, E. (2005), „Obliczanie maksymalnych stabilnych zbiorów dla grafów odległościowo-dziedzicznych”, Optymalizacja dyskretna , 2 (2): 185-188, doi : 10.1016/j.disopt.2005.03.004 , MR 2155518.
Corneil, Derek G .; Habiba, Michela; Lanlignel, Jean-Marc; Reed, Bruce ; Rotics, Udi (2012), „Polynomial-time recognition of clique-width $\leq 3$ graphs”, Discrete Applied Mathematics , 160 (6): 834–865, doi : 10.1016/j.dam.2011.03.020 , MR 2901093.
Corneil, Derek G .; Rotics, Udi (2005), „O relacji między szerokością kliki a szerokością drzewa”, SIAM Journal on Computing , 34 (4): 825-847, doi : 10.1137/S0097539701385351 , MR 2148860.
Courcelle, Bruno ; Engelfrieta, Joosta; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph grammars", Journal of Computer and System Sciences , 46 (2): 218-270, doi : 10.1016/0022-0000(93)90004-G , MR 1217156. Przedstawione w formie wstępnej w Gramatykach grafowych i ich zastosowaniu w informatyce (Bremen, 1990), MR 1431281 .
Courcelle, B. (1993), „Monadyczna logika drugiego rzędu i orientacja hipergrafów”, Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93) , s. 179-190, doi : 10.1109/LICS.1993.287589 , S2CID 39254668.
Courcelle, B .; Makowski, JA ; Rotics, U. (2000), „Linear time solvable Optimization problems on graphs on bounded clique width”, Theory of Computing Systems , 33 (2): 125–150, CiteSeerX 10.1.1.414.1845 , doi : 10.1007/s002249910009 , S2CID 15402031.
Courcelle, B .; Olariu, S. (2000), „Górne granice szerokości kliki wykresów” , Matematyka dyskretna , 101 (1–3): 77–144, doi : 10.1016/S0166-218X(99)00184-5.
Dworzak, Zdenek; Král', Daniel (2012), „Classes of graphs with small rank decompositions are χ-bounded”, Electronic Journal of Combinatorics , 33 (4): 679–683, arXiv : 1107.2161 , doi : 10.1016/j.ejc.2011.12. 005 , S2CID 5530520
Stypendyści, Michael R .; Rosamond, Frances A .; Rotics, Udi; Szeider, Stefan (2009), „Clique-width is NP-complete”, SIAM Journal on Discrete Mathematics , 23 (2): 909-939, doi : 10.1137/070687256 , MR 2519936.
Fomin, Fedor V.; Golovach, Petr A.; Łoksztanow, Daniel; Saurabh, Saket (2010), „Niewykonalność parametryzacji szerokości kliki”, SIAM Journal on Computing , 39 (5): 1941–1956, CiteSeerX 10.1.1.220.1712 , doi : 10.1137/080742270 , MR 2592039.
Golumbic, Martin Charles ; Rotics, Udi (2000), „O szerokości kliku niektórych doskonałych klas grafów”, International Journal of Foundations of Computer Science , 11 (3): 423-443, doi : 10.1142/S0129054100000260 , MR 1792124.
Gurski, Frank; Wanke, Egon (2000), „Szerokość drzewa grafów ograniczonych szerokością kliki bez $K n, n$ ”, w: Brandes, Ulrik ; Wagner, Dorothea (red.), Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Niemcy, 15-17 czerwca 2000, Proceedings , Lecture Notes in Computer Science, 1928 , Berlin: Springer, s. 196-205, doi : 10.1007/3-540-40064-8_19 , MR 1850348.
Gurski, Frank; Wanke, Egon (2007), "Wykresy liniowe ograniczonej szerokości kliki", Discrete Mathematics , 307 (22): 2734-2754, doi : 10.1016/j.disc.2007.01.020.
Gurski, Frank; Wanke, Egon (2009), "The NLC-width and clique-width for powers of graphed tree-width", Discrete Applied Mathematics , 157 (4): 583-595, doi : 10.1016/j.dam.2008.08. 031 , MR 2499471.
Hliněný, Petr; Oum, Sang-il (2008), "Finding branch-decompositions and rank-decompositions", SIAM Journal on Computing , 38 (3): 1012-1032, CiteSeerX 10.1.1.94.2272 , doi : 10.1137/070685920 , MR 2421076.
Oum, Sang-il ; Seymour, Paul (2006), "Przybliżenie szerokości kliki i szerokości gałęzi", Journal of Combinatorial Theory , Seria B, 96 (4): 514-528, doi : 10.1016/j.jctb.2005.10.006 , MR 2232389.
Oum, Sang-il (2009), „Szybkie przybliżanie szerokości rang i szerokości klik”, ACM Transactions on Algorithms , Notatki do wykładu z informatyki, 5 (1): art. 10, 20, CiteSeerX 10.1.1.574.8156 , doi : 10.1007/11604686_5 , ISBN 978-3-540-31000-6, MR 2479181.
Todinca, Ioan (2003), "Moc kolorowania grafów ograniczonej szerokości kliki", Koncepcje teorii grafów w informatyce , Notatki z wykładu w Comput. Sci., 2880 , Springer, Berlin, s. 370-382, doi : 10.1007/978-3-540-39890-5_32 , MR 2080095.
Wanke, Egon (1994), " $k-$ NLC wykresy i algorytmy wielomianowe", Discrete Applied Mathematics , 54 (2-3): 251-266, doi : 10.1016/0166-218X(94)90026-4 , MR 1300250.

Languages

In other projects