Cliquenbreite - Clique-width
In der Graphentheorie ist die Cliquenbreite eines Graphen ein Parameter, der die strukturelle Komplexität des Graphen beschreibt; es ist eng mit treewidth verwandt , aber im Gegensatz zu treewidth kann es sogar für dichte Graphen begrenzt werden . Es ist definiert als die minimale Anzahl von Labels, die benötigt werden, um mit den folgenden 4 Operationen zu konstruieren :
- Erstellung eines neuen Knotens v mit Label i ( notiert i(v) )
- Disjunkte Vereinigung zweier beschrifteter Graphen G und H (bezeichnet )
- Verbinden jeder Ecke mit der Bezeichnung i durch eine Kante mit jeder Ecke mit der Bezeichnung j (bezeichnet als η(i,j) ), wobei
- Umbenennen von Label i in Label j (bezeichnet als ρ ( i , j ) )
Graphen mit beschränkter Clique-Breite umfassen die Cographen und distanzerblichen Graphen . Obwohl es NP-schwer ist , die Cliquenbreite zu berechnen, wenn sie unbeschränkt ist, und unbekannt ist, ob sie in Polynomialzeit berechnet werden kann, wenn sie begrenzt ist, sind effiziente Näherungsalgorithmen für die Cliquenbreite bekannt. Basierend auf diesen Algorithmen und dem Theorem von Courcelle können viele Graphenoptimierungsprobleme, die für beliebige Graphen NP-schwer sind, schnell auf Graphen mit beschränkter Cliquenbreite gelöst oder approximiert werden.
Die dem Konzept der Cliquenbreite zugrunde liegenden Konstruktionssequenzen wurden 1990 von Courcelle , Engelfriet und Rozenberg sowie von Wanke (1994) formuliert . Der Name "Cliquenbreite" wurde von Chlebíková (1992) für ein anderes Konzept verwendet . 1993 hatte der Begriff bereits seine heutige Bedeutung.
Spezielle Klassen von Graphen
Cographen sind genau die Graphen mit einer Cliquenbreite von höchstens 2. Jeder entfernungserbliche Graph hat eine Cliquenbreite von höchstens 3. Die Cliquenbreite von Einheitsintervallgraphen ist jedoch (aufgrund ihrer Gitterstruktur) unbegrenzt. In ähnlicher Weise ist die Cliquenbreite von bipartiten Permutationsgraphen unbegrenzt (basierend auf einer ähnlichen Gitterstruktur). Basierend auf der Charakterisierung von Cographen als Graphen ohne induzierten Untergraphen, die zu einem sehnenlosen Pfad mit vier Scheitelpunkten isomorph sind, wurde die Cliquenbreite vieler Graphklassen, die durch verbotene induzierte Untergraphen definiert sind, klassifiziert.
Andere Graphen mit begrenzter Cliquenbreite umfassen die k- Blatt-Potenzen für begrenzte Werte von k ; dies sind die induzierten Teilgraphen der Blätter eines Baumes T in der Graphenstärke T k . Blattpotenzen mit unbegrenzten Exponenten haben jedoch keine begrenzte Cliquenbreite.
Grenzen
Courcelle & Olariu (2000) und Corneil & Rotics (2005) bewiesen die folgenden Grenzen für die Cliquenbreite bestimmter Graphen:
- Wenn ein Graph höchstens eine Cliquenbreite k hat , dann hat dies auch jeder induzierte Untergraph des Graphen.
- Der Komplementgraph eines Graphen der Cliquenbreite k hat eine Cliquenbreite von höchstens 2 k .
- Die Graphen der Baumbreite w haben höchstens Cliquenbreite 3 · 2 w − 1 . Die exponentielle Abhängigkeit in dieser Schranke ist notwendig: Es gibt Graphen, deren Cliquenbreite exponentiell größer ist als ihre Baumbreite. In der anderen Richtung können Graphen mit begrenzter Cliquenbreite eine unbegrenzte Baumbreite haben; zum Beispiel haben n -vertex vollständige Graphen die Cliquenbreite 2, aber die Baumbreite n − 1 . Jedoch haben Graphen der Cliquenbreite k , die keinen vollständigen bipartiten Graphen K t , t als Untergraph haben, eine Baumbreite von höchstens 3 k ( t − 1) − 1 . Daher ist für jede Familie von dünn besetzten Graphen eine begrenzte Baumbreite äquivalent zu einer begrenzten Cliquenbreite.
- Ein weiterer Graphparameter, die Rangbreite , wird in beide Richtungen durch die Cliquenbreite begrenzt: Rangbreite ≤ Cliquenbreite 2 Rangbreite + 1 .
Wenn außerdem ein Graph G eine Cliquenbreite k hat , dann hat die Graphenstärke G c eine Cliquenbreite von höchstens 2 kc k . Obwohl es eine exponentielle Lücke sowohl in der Schranke für die Cliquenbreite von der Baumbreite als auch der Schranke für die Cliquenbreite der Graphenpotenzen gibt, verbinden sich diese Schranken nicht: Wenn ein Graph G eine Baumbreite w hat , dann hat G c eine Cliquenbreite höchstens 2( c + 1) w + 1 − 2 , nur einfach exponentiell in der Baumbreite.
Rechenkomplexität
Können Graphen mit beschränkter Cliquenbreite in polynomieller Zeit erkannt werden?
Viele Optimierungsprobleme, die für allgemeinere Klassen von Graphen NP-schwer sind, können durch dynamische Programmierung auf Graphen begrenzter Cliquenbreite effizient gelöst werden , wenn eine Konstruktionssequenz für diese Graphen bekannt ist. Insbesondere hat jede Grapheigenschaft , die in MSO 1 monadischer Logik zweiter Ordnung (eine Form der Logik, die eine Quantifizierung über Sätze von Knoten ermöglicht) ausgedrückt werden kann, einen Linearzeitalgorithmus für Graphen mit beschränkter Cliquenbreite durch eine Form des Satzes von Courcelle .
Es ist auch möglich, optimale Graphfärbungen oder Hamilton-Zyklen für Graphen beschränkter Cliquenbreite in polynomialer Zeit zu finden, wenn eine Konstruktionsfolge bekannt ist, aber der Exponent des Polynoms mit der Cliquenbreite zunimmt und Beweise aus der Berechnungskomplexitätstheorie zeigen dass diese Abhängigkeit wahrscheinlich notwendig ist. Die Graphen mit beschränkter Clique-Breite sind χ- begrenzt , was bedeutet, dass ihre chromatische Zahl höchstens eine Funktion der Größe ihrer größten Clique ist.
Die Graphen der Cliquenbreite drei können in polynomieller Zeit unter Verwendung eines auf Split-Zerlegung basierenden Algorithmus erkannt und eine Konstruktionssequenz für sie gefunden werden . Für Graphen mit unbeschränkter Cliquenbreite ist es NP-schwer , die Cliquenbreite exakt zu berechnen, und auch NP-schwer, eine Approximation mit sublinearen additiven Fehlern zu erhalten. Wenn jedoch die Cliquenbreite begrenzt ist, ist es möglich, eine Konstruktionssequenz mit begrenzter Breite (exponentiell größer als die tatsächliche Cliquenbreite) in polynomieller Zeit zu erhalten. Es bleibt offen, ob die genaue Cliquenbreite oder eine engere Annäherung daran in festparametrischer lenkbarer Zeit berechnet werden kann, ob sie in polynomieller Zeit für jede feste Schranke der Cliquenbreite berechnet werden kann oder ob die Graphen der Cliquenbreite vier kann in polynomieller Zeit erkannt werden.
Beziehung zur Baumbreite
Die Theorie von Graphen mit beschränkter Cliquenbreite ähnelt der von Graphen mit beschränkter Baumbreite , erlaubt aber im Gegensatz zu Baumbreite dichte Graphen . Wenn eine Graphenfamilie eine begrenzte Cliquenbreite hat, dann hat sie entweder eine beschränkte Baumbreite oder jeder vollständige bipartite Graph ist ein Untergraph eines Graphen in der Familie. Baumbreite und Cliquenbreite sind auch durch die Theorie der Liniengraphen verbunden : Eine Familie von Graphen hat genau dann eine beschränkte Baumbreite, wenn ihre Liniengraphen eine beschränkte Cliquenbreite haben.
Anmerkungen
Verweise
- Brandstädt, A. ; Dragan, FF; Le, H.-O.; Mosca, R. (2005), "Neue Graphklassen von beschränkter Cliquenbreite", 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-Breite für 4-Vertex-verbotene Untergraphen", Theory of Computing Systems , 39 (4): 561–590, doi : 10.1007/s00224-005-1199-1 , S2CID 20050455.
- Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemäische Graphen und Intervallgraphen sind Blattpotenzen", LATIN 2008: Theoretische Informatik , Lecture Notes in Comput. Sci., 4957 , Springer, Berlin, S. 479–491, doi : 10.1007/978-3-540-78773-0_42 , MR 2472761.
- Brandstädt, A. ; Lozin, VV (2003), "On the linear structure and clique-width of bipartite permutation graphs", Ars Combinatoria , 67 : 273–281, CiteSeerX 10.1.1.16.2000.
- Chlebíková, J. (1992), "On the 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), "Computing maximum stable set for distance-hereditary graphs", Discrete Optimization , 2 (2): 185–188, doi : 10.1016/j.disopt.2005.03.004 , MR 2155518.
- Corneil, Derek G. ; Habib, Michel; Lanlignel, Jean-Marc; Schilf, Bruce ; Rotics, Udi (2012), "Polynomial-time detection of clique-width ≤ 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), "On the relation between clique-width and treewidth", SIAM Journal on Computing , 34 (4): 825–847, doi : 10.1137/S0097539701385351 , MR 2148860.
- Courcelle, Bruno ; Engelfriet, Joost; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph gramars", Journal of Computer and System Sciences , 46 (2): 218–270, doi : 10.1016/0022-0000(93)90004-G , MR 1217156. In vorläufiger Form präsentiert in Graph-Grammatiken und ihre Anwendung auf die Informatik (Bremen, 1990), MR 1431281 .
- Courcelle, B. (1993), "Monadische Logik zweiter Ordnung und Hypergraph-Orientierung", 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. ; Makowsky, JA ; Rotics, U. (2000), "Linear time solvable Optimization Problems on graphs onbounded 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), "Obere Grenzen für die Cliquenbreite von Graphen" , Discrete Applied Mathematics , 101 (1–3): 77–144, doi : 10.1016/S0166-218X(99)00184-5.
- Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank Decorations are χ-bounded", 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-width parametrizations", 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), "Die Baumbreite von Clique-Breiten-begrenzten Graphen ohne K n,n ", in Brandes, Ulrik ; Wagner, Dorothea (Hrsg.), Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Deutschland, 15.–17. Juni 2000, Proceedings , Lecture Notes in Computer Science, 1928 , Berlin: Springer, pp. 196–205, doi : 10.1007/3-540-40064-8_19 , MR 1850348.
- Gurski, Frank; Wanke, Egon (2007), "Line graphs ofbounded clique-width", 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 graphs ofbounded tree-width", Discrete Applied Mathematics , 157 (4): 583–595, doi : 10.1016/j.dam.2008.08. 031 , MR 2.499.471.
- 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 , Serie 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 quick", ACM Transactions on Algorithms , Vorlesungsnotizen in Informatik, 5 (1): Art.-Nr. 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 ofbounded clique-width", Graphentheoretische Konzepte in der Informatik , Lecture Notes in Comput. Sci., 2880 , Springer, Berlin, S. 370–382, doi : 10.1007/978-3-540-39890-5_32 , MR 2080095.
- Wanke, Egon (1994), " k -NLC graphs and polynomial algorithms", Discrete Applied Mathematics , 54 (2–3): 251–266, doi : 10.1016/0166-218X(94)90026-4 , MR 1300250.
