Klickbredd - Clique-width
I grafteori , den klick-bredden av en graf är en parameter som beskriver den strukturella komplexiteten av grafen; det är nära besläktat med trädbredd , men till skillnad från trädbredd kan det begränsas även för täta grafer . Det definieras som det minsta antal etiketter som behövs för att konstruera med hjälp av följande 4 operationer:
- Skapande av en ny toppunkt v med etikett i (noterad i (v) )
- Oförenad förening av två märkta grafer G och H (betecknade )
- Anslutning med en kant varje hörn märkt i till varje hörn märkt j (betecknad η (i, j) ), där
- Byt namn på etikett i till etikett j (betecknad ρ ( i , j ))
Grafer med begränsad klickbredd inkluderar cographs och avståndsärftliga grafer . Även om det är NP-svårt att beräkna klickbredden när den är obegränsad och okänt om den kan beräknas i polynomtid när den är begränsad, är effektiva approximationsalgoritmer för klickbredden kända. Baserat på dessa algoritmer och på Courcelles teorem kan många grafoptimeringsproblem som är NP-hårda för godtyckliga grafer lösas eller approximeras snabbt på graferna med begränsad klickbredd.
De konstruktionssekvenser som ligger till grund för begreppet klickbredd formulerades av Courcelle , Engelfriet och Rozenberg 1990 och av Wanke (1994) . Namnet "klickbredd" användes för ett annat koncept av Chlebíková (1992) . År 1993 hade termen redan sin nuvarande betydelse.
Särskilda klasser av grafer
Cographs är exakt graferna med högst klickbredd 2. Varje distansärftlig graf har högst klickbredd 3. Dock är klickbredden på enhetsintervallgrafer obegränsad (baserat på deras rutnätstruktur). På samma sätt är klickbredden för bipartitpermutationsgrafer obegränsad (baserad på liknande rutnätstruktur). Baserat på karaktäriseringen av kataloger som graferna utan inducerad subgraf isomorf till en ackordlös väg med fyra hörn, har klickbredden för många grafklasser definierade av förbjudna inducerade subgrafer klassificerats.
Andra grafer med begränsad klickbredd inkluderar k -bladkraften för begränsade värden av k ; dessa är de inducerade subgrafer av bladen på ett träd T i grafen effekt T k . Bladkraft med obegränsade exponenter har dock inte begränsad klickbredd.
Gräns
Courcelle & Olariu (2000) och Corneil & Rotics (2005) visade följande gränser för klickbredden på vissa grafer:
- Om en graf har klickbredd som högst k , så gör varje inducerad delgraf av grafen.
- Den komplementgraf av en graf av klick-bredd k har klick-bredd som mest 2 k .
- Graferna för trebredd w har högst klickbredd 3,2 w- 1 . Det exponentiella beroendet i denna gräns är nödvändigt: det finns grafer vars klickbredd är exponentiellt större än deras trädbredd. I den andra riktningen kan grafer med begränsad klickbredd ha obegränsad trädbredd; till exempel, n -vertex komplett graf har klick-bredd 2 men treewidth n - 1 . Grafer med klickbredd k som inte har någon fullständig bipartitgraf K t , t som subgraf har dock högst 3 k ( t- 1)-1 . Därför är det för varje familj av glesa grafer att ha begränsad trädbredd ekvivalent med att ha begränsat klickbredd.
- En annan grafparameter, rankbredden , begränsas i båda riktningarna av klickbredden: rankbredd ≤ klickbredd ≤ 2 rankbredd + 1 .
Dessutom, om en graf G har klick-bredd k , då grafen effekten G c har klick-bredd som mest två kc k . Även om det finns ett exponentiellt gap i både gränsen för klickbredd från trädbredd och gränsen för klickbredd för grafeffekter, förenar dessa gränser inte varandra: om en graf G har trebredd w , har G c klickbredd högst 2 ( c + 1) w + 1 - 2 , enbart exponentiellt i trädbredden.
Beräkningskomplexitet
Kan grafer med begränsad klickbredd igenkännas under polynomtid?
Många optimeringsproblem som är NP-hårda för mer allmänna klasser av grafer kan lösas effektivt genom dynamisk programmering på grafer med begränsad klickbredd, när en konstruktionssekvens för dessa grafer är känd. I synnerhet har varje grafegenskap som kan uttryckas i MSO 1 monadisk andra ordnings logik (en form av logik som möjliggör kvantifiering över uppsättningar av hörn) en linjär tidsalgoritm för grafer med begränsad klickbredd, med en form av Courcelles teorem .
Det är också möjligt att hitta optimala graffärgningar eller Hamiltoniska cykler för grafer med begränsad klickbredd i polynomtid, när en konstruktionssekvens är känd, men exponenten för polynomet ökar med klickbredden, och bevis från beräkningskomplexitetsteori visar att detta beroende sannolikt kommer att vara nödvändigt. Graferna för begränsad klickbredd är χ -gränsade , vilket betyder att deras kromatiska tal högst är en funktion av storleken på deras största klick.
Graferna för klickbredd tre kan kännas igen och en konstruktionssekvens hittas för dem i polynomtid med hjälp av en algoritm baserad på delad sönderdelning . För grafer med obegränsad klickbredd är det NP-svårt att beräkna klickbredden exakt, och även NP-svårt att få en approximation med sublinjärt additivfel. När klickbredden är begränsad är det emellertid möjligt att erhålla en konstruktionssekvens med begränsad bredd (exponentiellt större än den verkliga klickbredden) under polynomtid. Det förblir öppet om den exakta klickbredden eller en närmare tillnärmning till den kan beräknas i fast parametervärdbar tid , om den kan beräknas i polynomtid för varje fast gräns på klickbredden eller till och med om graferna med klickbredd fyra kan kännas igen på polynomtid.
Förhållande till trädbredd
Teorin om grafer för begränsad klickbredd liknar den för grafer över begränsad trädbredd , men till skillnad från trädbredd möjliggör täta grafer . Om en familj av grafer har begränsat klickbredd, så har den antingen begränsat trädbredden eller så är varje fullständig bipartitgraf en delgraf av en graf i familjen. Trebredd och klickbredd är också kopplade genom teorin om linjediagram : en familj av grafer har begränsat trädbredden om och bara om deras linjediagram har begränsat klickbredd.
Anteckningar
Referenser
- Brandstädt, A .; Dragan, FF; Le, H.-O .; Mosca, R. (2005), "New graph classes of bounded clique-width", Theory of Computing Systems , 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 forbidden subgraphs", Theory of Computing Systems , 39 (4): 561–590, doi : 10.1007/s00224-005-1199-1 , S2CID 20050455.
- Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaiska grafer och intervallgrafer är bladkrafter ", LATIN 2008: Teoretisk informatik , Föreläsningsanteckningar i beräkning. Sci., 4957 , Springer, Berlin, sid. 479–491, doi : 10.1007/978-3-540-78773-0_42 , MR 2472761.
- Brandstädt, A .; Lozin, VV (2003), "Om den linjära strukturen och klickbredden för tvåpartspermutationsgrafer", Ars Combinatoria , 67 : 273–281, CiteSeerX 10.1.1.16.2000.
- Chlebíková, J. (1992), "On a tree-width of a graph", Acta Mathematica Universitatis Comenianae , New Series, 61 (2): 225–236, CiteSeerX 10.1.1.30.3900 , MR 1205875.
- Cogis, O .; Thierry, E. (2005), "Beräkning av maximala stabila uppsättningar för avståndsärftliga grafer", Diskret optimering , 2 (2): 185–188, doi : 10.1016/j.disopt.2005.03.004 , MR 2155518.
- Corneil, Derek G .; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce ; Rotics, Udi (2012), "Polynom-tidigenkänning av klickbredd ≤ 3 grafer", Diskret tillämpad matematik , 160 (6): 834–865, doi : 10.1016/j.dam.2011.03.020 , MR 2901093.
- Corneil, Derek G .; Rotics, Udi (2005), "Om förhållandet mellan klickbredd och trädbredd", SIAM Journal on Computing , 34 (4): 825–847, doi : 10.1137/S0097539701385351 , MR 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 , MR 1217156. Presenteras i preliminär form i Graph grammars och deras tillämpning på datavetenskap (Bremen, 1990), MR 1431281 .
- Courcelle, B. (1993), "Monadic second-order logic and hypergraph orientation", Proceedings of Åttonde årliga IEEE-symposium om logik i datavetenskap (LICS '93) , s. 179–190, doi : 10.1109/LICS.1993.287589 , S2CID 39254668.
- Courcelle, B .; Makowsky, JA ; Rotics, U. (2000), "Linjär tidslösliga optimeringsproblem på grafer på begränsad klickbredd", 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), "Övre gränser för grafens klickbredd" , Diskret tillämpad matematik , 101 (1–3): 77–144, doi : 10.1016/S0166-218X (99) 00184-5.
- Dvořák, Zdeněk; Král ', Daniel (2012), "Klasser av grafer med små rangnedbrytningar är χ-begränsade", 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), "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 .; Lokshtanov, Daniel; Saurabh, Saket (2010), "Intractability of clique-wide parameterizations", 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), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science , 11 (3): 423–443, doi : 10.1142/S0129054100000260 , MR 1792124.
- Gurski, Frank; Wanke, Egon (2000), "Trädbredden på klickbreddsbegränsade grafer utan K n, n ", i Brandes, Ulrik ; Wagner, Dorothea (red.), Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Tyskland, 15–17 juni 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), "Linjediagram över begränsad klickbredd", Diskret matematik , 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", Diskret tillämpad matematik , 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), "Approximating clique-width and branch-width", Journal of Combinatorial Theory , Series B, 96 (4): 514–528, doi : 10.1016/j.jctb.2005.10.006 , MR 2232389.
- Oum, Sang-il (2009), "Approximating rank-width and clique-width snel", ACM Transactions on Algorithms , Lecture Notes in Computer Science, 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), "Coloring powers of graphs of bounded clique-width", Grafteoretiska begrepp i datavetenskap , Föreläsningsanteckningar i beräkning. Sci., 2880 , Springer, Berlin, s. 370–382, doi : 10.1007/978-3-540-39890-5_32 , MR 2080095.
- Wanke, Egon (1994), " k -NLC-grafer och polynomalgoritmer", Diskret tillämpad matematik , 54 (2–3): 251–266, doi : 10.1016/0166-218X (94) 90026-4 , MR 1300250.