Šířka kliky - Clique-width
v teorie grafů, šířka kliky a graf je parametr, který popisuje strukturální složitost grafu; úzce souvisí s šířka stromu, ale na rozdíl od šířky stromu ji lze omezit i pro husté grafy Je definován jako minimální počet štítků potřebných ke konstrukci pomocí následujících 4 operací:
- Vytvoření nového vrcholu proti se štítkem i (uvedeno já (v) )
- Nespojené spojení dvou označených grafů G a H (označeno )
- Spojení hranou každého označeného vrcholu i ke každému označenému vrcholu j (označeno η (i, j)), kde
- Přejmenování štítku i označit j (označeno ρ(i,j) )
Grafy ohraničené šířky kliky zahrnují cographs a vzdálenostně dědičné grafy. I když je NP-tvrdé vypočítat šířku kliky, když je neomezená, a není známo, zda ji lze vypočítat v polynomiálním čase, když je omezená, efektivní aproximační algoritmy pro šířku kliky jsou známy. Na základě těchto algoritmů a dále Courcelleova věta, mnoho problémů s optimalizací grafů, které jsou pro libovolné grafy NP-těžké, lze rychle vyřešit nebo aproximovat na grafech omezené šířky kliky.
Konstrukční sekvence, na nichž je založen koncept šířky kliky, byly formulovány pomocí Courcelle, Engelfriet a Rozenberg v roce 1990[1] a tím Wanke (1994). Název „šířka kliky“ použil pro jiný koncept Chlebíková (1992). Do roku 1993 měl tento pojem již svůj současný význam.[2]
Speciální třídy grafů
Cographs jsou přesně grafy s maximální šířkou kliky 2.[3] Každý vzdálenost-dědičný graf má šířku kliky maximálně 3. Šířka kliky grafů jednotkových intervalů je však neomezená (na základě jejich struktury mřížky).[4] Podobně je šířka kliky bipartitních permutačních grafů neomezená (na základě podobné struktury mřížky).[5] Na základě charakterizace grafů, protože grafy bez indukovaného podgrafu jsou izomorfní vůči akordové cestě se čtyřmi vrcholy, byla klasifikována šířka kliky mnoha tříd grafů definovaných zakázanými indukovanými podgrafy.[6]
Mezi další grafy s omezenou šířkou kliky patří k- listové síly pro omezené hodnoty k; tohle jsou indukované podgrafy listů stromu T v výkon grafu Tk. Listové síly s neomezenými exponenty však nemají ohraničenou šířku kliky.[7]
Meze
Courcelle & Olariu (2000) a Corneil & Rotics (2005) prokázal následující hranice šířky kliky určitých grafů:
- Pokud má graf nanejvýš šířku kliky k, pak to dělá každý indukovaný podgraf grafu.[8]
- The doplňkový graf grafu šířky kliky k má nanejvýš šířku kliky 2k.[9]
- Grafy šířka stromu w mít maximálně šířku kliky 3 · 2w − 1. Exponenciální závislost v této vazbě je nutná: existují grafy, jejichž šířka kliky je exponenciálně větší než jejich šířka stromu.[10] V opačném směru mohou mít grafy ohraničené šířky kliky neomezenou šířku stromu; například, n-vrchol kompletní grafy mají šířku kliky 2, ale šířku stromu n − 1. Nicméně, grafy o šířce kliky k které nemají č kompletní bipartitní graf K.t,t jako podgraf mají maximální šířku stromu 3k(t − 1) − 1. Proto pro každou rodinu řídké grafy, mít omezenou šířku stromu je ekvivalentní mít omezenou šířku kliky.[11]
- Další parametr grafu, šířka pozice, je v obou směrech ohraničena šířkou kliky: rank-width ≤ clique-width ≤ 2rank-width + 1.[12]
Navíc, pokud graf G má šířku kliky k, pak výkon grafu GC má nanejvýš šířku kliky 2kck.[13] Ačkoli existuje exponenciální mezera v mezích pro šířku kliky od šířky stromu a ve vazbě pro šířku kliky mocností grafu, tyto hranice se navzájem neslučují: pokud je graf G má šířku stromu w, pak GC má nanejvýš šířku kliky 2(C + 1)w + 1 − 2, pouze jednotlivě exponenciální v šířce stromu.[14]
Výpočetní složitost
 | Nevyřešený problém v matematice: Lze grafy ohraničené šířky kliky rozpoznat v polynomiálním čase? (více nevyřešených úloh z matematiky) |
Mnoho optimalizačních problémů, které jsou NP-tvrdé pro obecnější třídy grafů lze efektivně vyřešit pomocí dynamické programování na grafech s omezenou šířkou kliky, pokud je známa konstrukční posloupnost těchto grafů.[15][16] Zejména každý vlastnost grafu které lze vyjádřit v MSO1 monadická logika druhého řádu (forma logiky umožňující kvantifikaci přes množiny vrcholů) má algoritmus lineárního času pro grafy ohraničené šířky kliky, formou Courcelleova věta.[16]
Je také možné najít optimální barvení grafů nebo Hamiltonovské cykly pro grafy ohraničené šířky kliky v polynomiálním čase, když je známa konstrukční sekvence, ale exponent polynomu se zvyšuje se šířkou kliky a důkazy z teorie výpočetní složitosti ukazují, že tato závislost bude pravděpodobně nezbytná.[17]Grafy ohraničené šířky kliky jsou χ- omezený, což znamená, že jejich chromatický počet je nanejvýš funkcí velikosti jejich největší kliky.[18]
Grafy šířky kliky tři lze rozpoznat a najít pro ně konstrukční sekvenci v polynomiálním čase pomocí algoritmu založeného na dělený rozklad.[19]U grafů neomezené šířky kliky to je NP-tvrdé přesně vypočítat šířku kliky a také NP-hard získat aproximaci s sublearní aditivní chybou.[20] Když je však šířka kliky ohraničená, je možné získat konstrukční sekvenci ohraničené šířky (exponenciálně větší než skutečná šířka kliky) v polynomiálním čase.[21] Zůstává otevřené, zda lze vypočítat přesnou šířku kliky nebo její těsnější přiblížení fixovatelný čas strávitelný parametrem, zda ji lze vypočítat v polynomiálním čase pro každou pevnou vazbu na šířku kliky, nebo dokonce, zda lze grafy šířky kliky čtyři rozpoznat v polynomiálním čase.[20]
Vztah k šířce stromu
Teorie grafů ohraničené šířky kliky se podobá teorii grafů ohraničené šířka 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 všechny kompletní bipartitní graf je podgraf grafu v rodině.[11] Šířka stromu a šířka kliky jsou také spojeny prostřednictvím teorie spojnicové grafy: rodina grafů má omezenou šířku stromu právě tehdy, pokud jejich spojnicové grafy mají omezenou šířku kliky.[22]
Poznámky
- ^ Courcelle, Engelfriet a Rozenberg (1993).
- ^ Courcelle (1993).
- ^ Courcelle & Olariu (2000).
- ^ Golumbic & Rotics (2000).
- ^ Brandstädt & Lozin (2003).
- ^ Brandstädt a kol. (2005); Brandstädt a kol. (2006).
- ^ Brandstädt & Hundt (2008); Gurski & Wanke (2009).
- ^ Courcelle & Olariu (2000), Dodatek 3.3.
- ^ Courcelle & Olariu (2000), Věta 4.1.
- ^ Corneil & Rotics (2005), posilování Courcelle & Olariu (2000), Věta 5.5.
- ^ A b Gurski & Wanke (2000).
- ^ Oum & Seymour (2006).
- ^ Todinca (2003).
- ^ Gurski & Wanke (2009).
- ^ Cogis & Thierry (2005).
- ^ A b Courcelle, Makowsky & Rotics (2000).
- ^ Fomin a kol. (2010).
- ^ Dvořák & Král '(2012).
- ^ Corneil a kol. (2012).
- ^ A b Fellows a kol. (2009).
- ^ Oum & Seymour (2006); Hliněný & Oum (2008); Oum (2009).
- ^ Gurski & Wanke (2007).
Reference
- Brandstädt, A.; Dragan, F.F .; Le, H.O .; Mosca, R. (2005), „Nové třídy grafů ohraničené šířky kliky“, Teorie výpočetních systémů, 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, V.V. (2006), „Clique-width pro 4grafy zakázané subgrafy“, Teorie výpočetních systémů, 39 (4): 561–590, doi:10.1007 / s00224-005-1199-1, S2CID 20050455.
- Brandstädt, Andreas; Hundt, Christian (2008), „Ptolemaiovské grafy a intervalové grafy jsou listové síly“, LATIN 2008: Teoretická informatika, Poznámky k přednášce ve Výpočtu. Sci., 4957, Springer, Berlín, str. 479–491, doi:10.1007/978-3-540-78773-0_42, PAN 2472761.
- Brandstädt, A.; Lozin, V.V. (2003), „O lineární struktuře a šířce kliky bipartitních permutačních grafů“, Ars Combinatoria, 67: 273–281, CiteSeerX 10.1.1.16.2000.
- Chlebíková, J. (1992), „Na stromové šířce grafu“, Acta Mathematica Universitatis ComenianaeNová řada, 61 (2): 225–236, CiteSeerX 10.1.1.30.3900, PAN 1205875.
- Cogis, O .; Thierry, E. (2005), „Výpočet maximálně stabilních množin pro grafy dědičné pro vzdálenost“, Diskrétní optimalizace, 2 (2): 185–188, doi:10.1016 / j.disopt.2005.03.004, PAN 2155518.
- Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi (2012), „Polynomial-time recognition of clique-width ≤ 3 grafy ", Diskrétní aplikovaná matematika, 160 (6): 834–865, doi:10.1016 / j.dam.2011.03.020, PAN 2901093.
- Corneil, Derek G.; Rotics, Udi (2005), „O vztahu mezi šířkou kliky a šířkou stromu“, SIAM Journal on Computing, 34 (4): 825–847, doi:10.1137 / S0097539701385351, PAN 2148860.
- Courcelle, Bruno; Engelfriet, Joost; 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, PAN 1217156. Prezentováno v předběžné formě v Graph grammars and their application to computer science (Bremen, 1990), PAN1431281.
- Courcelle, B. (1993), „Monadická logika druhého řádu a orientace hypergrafu“, Sborník z osmého výročního sympozia IEEE o logice v informatice (LICS '93), str. 179–190, doi:10.1109 / LICS.1993.287589, S2CID 39254668.
- Courcelle, B.; Makowsky, J. A.; Rotics, U. (2000), „Problémy s optimalizací lineárního času v grafech na omezené šířce kliky“, Teorie výpočetních systémů, 33 (2): 125–150, CiteSeerX 10.1.1.414.1845, doi:10,1007 / s002249910009, S2CID 15402031.
- Courcelle, B.; Olariu, S. (2000), "Horní hranice k šířce kliky grafů", Diskrétní aplikovaná matematika, 101 (1–3): 77–144, doi:10.1016 / S0166-218X (99) 00184-5.
- Dvořák, Zdeněk; Král ', Daniel (2012), „Třídy grafů s malými řadovými rozklady jsou χ-ohraničené“, Electronic Journal of Combinatorics, 33 (4): 679–683, arXiv:1107.2161, doi:10.1016 / j.ejc.2011.12.005, S2CID 5530520
- Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), „Šířka kliky je NP-úplná“, SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, PAN 2519936.
- Fomin, Fedor V .; Golovach, Petr A .; Lokshtanov, Daniel; Saurabh, Saket (2010), „Intractability of clique-width parameterizations“, SIAM Journal on Computing, 39 (5): 1941–1956, CiteSeerX 10.1.1.220.1712, doi:10.1137/080742270, PAN 2592039.
- Golumbic, Martin Charles; Rotics, Udi (2000), „Na šířku kliky některých dokonalých tříd grafů“, International Journal of Foundations of Computer Science, 11 (3): 423–443, doi:10.1142 / S0129054100000260, PAN 1792124.
- Gurski, Frank; Wanke, Egon (2000), „Stromová šířka grafů ohraničených šířkou kliky bez K.n, n", Brandes, Ulrik; Wagner, Dorothea (eds.), Graficko-teoretické koncepty v informatice: 26. mezinárodní workshop, WG 2000, Konstanz, Německo, 15. – 17. Června 2000, sborník, Přednášky v informatice, 1928, Berlín: Springer, s. 196–205, doi:10.1007/3-540-40064-8_19, PAN 1850348.
- Gurski, Frank; Wanke, Egon (2007), „Čárové grafy ohraničené šířky kliky“, Diskrétní matematika, 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 graphs of bounded tree-width“, Diskrétní aplikovaná matematika, 157 (4): 583–595, doi:10.1016 / j.dam.2008.08.031, PAN 2499471.
- Hliněný, Petr; Oum, Sang-il (2008), „Hledání větvových rozkladů a řadových rozkladů“, SIAM Journal on Computing, 38 (3): 1012–1032, CiteSeerX 10.1.1.94.2272, doi:10.1137/070685920, PAN 2421076.
- Oum, Sang-il; Seymour, Paule (2006), „Přibližná šířka kliky a šířka větve“, Journal of Combinatorial Theory, Řada B, 96 (4): 514–528, doi:10.1016 / j.jctb.2005.10.006, PAN 2232389.
- Oum, Sang-il (2009), „Rychlá přibližná šířka a šířka kliky“, Transakce ACM na algoritmech, Přednášky v informatice, 5 (1): Čl. 10, 20, CiteSeerX 10.1.1.574.8156, doi:10.1007/11604686_5, ISBN 978-3-540-31000-6, PAN 2479181.
- Todinca, Ioan (2003), „Barvicí síly grafů ohraničené šířky kliky“, Grafově-teoretické pojmy v informatice, Poznámky k přednášce ve Výpočtu. Sci., 2880, Springer, Berlín, str. 370–382, doi:10.1007/978-3-540-39890-5_32, PAN 2080095.
- Wanke, Egon (1994), "k-NLC grafy a polynomiální algoritmy ", Diskrétní aplikovaná matematika, 54 (2–3): 251–266, doi:10.1016 / 0166-218X (94) 90026-4, PAN 1300250.