Klikněte na Šířka

V teorii grafů je kliková šířka grafu  parametr, který popisuje strukturální složitost grafu. Parametr úzce souvisí s treewidth , ale na rozdíl od treewidth lze šířku kliky omezit i pro husté grafy . Šířka kliknutí je definována jako minimální počet štítků potřebný k vytvoření pomocí následujících 4 operací

  1. Vytvoření nového vrcholu v se štítkem i ( operace i(v) )
  2. Odpojené spojení dvou označených grafů G a H (operace )
  3. Hranové spojení každého vrcholu se štítkem i s každým vrcholem se štítkem j (operace η(i, j) ), kde
  4. Přejmenujte štítek i na j (operace ρ ( i , j ))

Grafy s ohraničenou šířkou kliky zahrnují kografy a grafy zděděné vzdáleností . Ačkoli je výpočet šířky kliky NP-obtížný , vzhledem k tomu, že není známa horní hranice a není známo, zda ji lze vypočítat v polynomiálním čase, když je známa horní hranice, jsou známy účinné aproximační algoritmy pro výpočet šířky kliky. Na základě těchto algoritmů a Courcelleova teorému lze mnoho optimalizačních problémů na grafech, které jsou NP-obtížné pro libovolné grafy, rychle vyřešit nebo aproximovat pro grafy s omezenou šířkou kliky.

Konstrukční sekvence, na kterých je založen pojem šířky kliky, formulovali Courcelle, Engelfried a Rosenberg v roce 1990 [1] a Vanke [2] . Název „šířka kliknutí“ použil pro další koncept Khlebikov [3] . Od roku 1993 se tento termín používá v jeho moderním smyslu [4] .

Speciální třídy grafů

Cographs  jsou přesně grafy s šířkou kliky nejvýše dvě [5] . Jakýkoli graf zděděný vzdáleností má šířku kliky nepřesahující 3. Šířka kliky intervalových grafů však není omezena (podle mřížkové struktury) [6] . Podobně není omezena šířka kliky u bipartitních permutačních grafů (podle podobné mřížkové struktury) [7] . Na základě popisu kografů jako grafů bez generovaných podgrafů izomorfních k cestám bez tětiv byla klasifikována šířka kliky mnoha tříd grafů definovaných zakázanými generovanými podgrafy [8] [9] .

Dalšími grafy s omezenou šířkou kliky jsou k - listové mocniny pro ohraničené hodnoty k , tedy vygenerované podgrafy listů stromu T na stupeň grafu T k . Stupeň listů s neomezeným exponentem však nemá omezenou šířku listu [10] [11] .

Hranice

Courcelle a Olariu [5] , stejně jako Corneil a Rotix [12] , uvedli následující hranice šířky kliky některých grafů:

Navíc, pokud má graf G šířku kliky k , pak stupeň grafu Gc má šířku kliky nepřesahující 2 kc k [18] . Ačkoli existuje exponenciála v nerovnostech šířky kliky ve srovnání s šířkou stromu a stupněm grafu, tyto hranice nedávají superpozici – pokud má graf G šířku stromu w , pak Gc má šířku kliky maximálně 2( c + 1) w + 1 − 2 , jen prostý exponent šířky stromu [11] .

Výpočetní složitost

Nevyřešené problémy v matematice : Lze graf s omezenou šířkou kliky rozpoznat v polynomiálním čase?

Mnoho optimalizačních problémů, které jsou NP-obtížné pro obecnější třídy grafů, lze efektivně vyřešit pomocí dynamického programování na grafech s omezenou šířkou kliky, pokud je známa posloupnost konstrukce těchto grafů [19] [20] . Konkrétně každý grafový invariant , který lze vyjádřit v MSO 1 ( jednomístná logika druhého řádu , druh logiky druhého řádu, která umožňuje kvantifikátory nad sadami vrcholů) má algoritmus lineárního času pro omezenou šířku grafy, jednou z formulací Courcelleovy věty [20] . Lze také nalézt optimální zbarvení nebo hamiltonovské cykly ohraničených grafů šířky kliky v polynomiálním čase, pokud je známa posloupnost konstrukce grafu, ale stupeň polynomu se zvyšuje s šířkou kliky a argumenty z teorie výpočetní složitosti ukazují, že taková závislost se zdá být být nevyhnutelný [21] .

Grafy se šířkou kliky tři lze rozpoznat a jejich konstrukční sekvenci lze nalézt v polynomiálním čase pomocí algoritmu založeného na dělené dekompozici [22] . Pro třídy grafů s neomezenou šířkou kliky je výpočet přesné šířky kliky NP-těžký a je také NP-obtížné získat aproximaci se sublineární aditivní chybou [23] . Pokud je však známa horní hranice šířky kliky, je možné získat posloupnost konstrukce grafu s omezenou šířkou (exponenciálně větší než skutečná šířka kliky) v polynomiálním čase [17] [24] [25] . Zůstává otevřenou otázkou, zda lze přesnou šířku kliky nebo blízkou aproximaci vypočítat v pevně-parametricky rozlišitelném čase, zda ji lze vypočítat v polynomiálním čase pro grafy s libovolnou pevnou hranicí šířky kliky, nebo dokonce, zda grafy s šířkou kliky o šířce čtyři jsou rozpoznány v polynomiálním čase [23] .

Odkaz na šířku dřeva

Teorie ohraničených klikových grafů má podobnosti s teorií ohraničených grafů šířky stromu , ale na rozdíl od šířky stromu umožňuje husté grafy . Pokud má rodina grafů omezenou šířku kliky, pak má buď omezenou šířku stromu, nebo jakýkoli kompletní bipartitní graf je podgrafem nějakého grafu v rodině [16] . Šířka stromu a šířka kliky také souvisí s teorií čárových grafů  — rodina grafů má omezenou šířku stromu právě tehdy, když jejich čárové grafy mají omezenou šířku kliky [26] .

Poznámky

  1. ↑ Courcelle, Engelfriet, Rozenberg, 1993 .
  2. ↑ Wanke, 1994 .
  3. ↑ Chlebíková, 1992 .
  4. ↑ Courcelle, 1993 .
  5. ↑ 12 Courcelle, Olariu, 2000 .
  6. ↑ Golumbic, Rotics, 2000 .
  7. ↑ Brandstädt, Lozin, 2003 .
  8. ↑ Brandstädt, Dragan, Le, Mosca, 2005 .
  9. ↑ Brandstädt, Engelfriet, Le, Lozin, 2006 .
  10. ↑ Brandstädt, Hundt, 2008 .
  11. ↑ 12 Gurski , Wanke, 2009 .
  12. ↑ Corneil, Rotics, 2005 .
  13. ↑ Courcelle, Olariu, 2000 , str. Důsledek 3.3.
  14. ↑ Courcelle, Olariu, 2000 , str. Věta 4.1.
  15. ↑ Corneil, Rotics, 2005 , Posilování - Courcelle, Olariu, 2000 , Věta 5.5.
  16. ↑ 12 Gurski , Wanke, 2000 .
  17. ↑ 12 Oum , Seymour, 2006 .
  18. ↑ Todinca, 2003 .
  19. ↑ Cogis, Thierry, 2005 .
  20. ↑ 12 Courcelle, Makowsky, Rotics, 2000 .
  21. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2010 .
  22. ↑ Corneil a kol., 2012 .
  23. ↑ 1 2 Fellows, Rosamond, Rotics, Szeider, 2009 .
  24. ↑ Hliněny, Oum, 2008 .
  25. ↑ Oum, 2009 .
  26. ↑ Gurski, Wanke, 2007 .

Literatura