Clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations :
- Creation of a new vertex v with label i ( noted i(v) )
- Disjoint union of two labeled graphs G and H ( denoted )
- Joining by an edge every vertex labeled i to every vertex labeled j (denoted η(i,j)), where
- Renaming label i to label j ( denoted ρ(i,j) )
Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for the clique-width are known. Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary graphs can be solved or approximated quickly on the graphs of bounded clique-width.
The construction sequences underlying the concept of clique-width were formulated by Courcelle, Engelfriet, and Rozenberg in 1990[1] and by Wanke (1994). The name "clique-width" was used for a different concept by Chlebíková (1992). By 1993, the term already had its present meaning.[2]
Special classes of graphs
Cographs are exactly the graphs with clique-width at most 2.[3] Every distance-hereditary graph has clique-width at most 3. However, the clique-width of unit interval graphs is unbounded (based on their grid structure).[4] Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure).[5] Based on the characterization of cographs as the graphs without induced subgraph isomorphic to a chordless path with four vertices, the clique-width of many graph classes defined by forbidden induced subgraphs has been classified.[6]
Other graphs with bounded clique-width include the k-leaf powers for bounded values of k; these are the induced subgraphs of the leaves of a tree T in the graph power Tk. However, leaf powers with unbounded exponents do not have bounded clique-width.[7]
Bounds
Courcelle & Olariu (2000) and Corneil & Rotics (2005) proved the following bounds on the clique-width of certain graphs:
- If a graph has clique-width at most k, then so does every induced subgraph of the graph.[8]
- The complement graph of a graph of clique-width k has clique-width at most 2k.[9]
- The graphs of treewidth w have clique-width at most 3 · 2w − 1. The exponential dependence in this bound is necessary: there exist graphs whose clique-width is exponentially larger than their treewidth.[10] In the other direction, graphs of bounded clique-width can have unbounded treewidth; for instance, n-vertex complete graphs have clique-width 2 but treewidth n − 1. However, graphs of clique-width k that have no complete bipartite graph Kt,t as a subgraph have treewidth at most 3k(t − 1) − 1. Therefore, for every family of sparse graphs, having bounded treewidth is equivalent to having bounded clique-width.[11]
- Another graph parameter, the rank-width, is bounded in both directions by the clique-width: rank-width ≤ clique-width ≤ 2rank-width + 1.[12]
Additionally, if a graph G has clique-width k, then the graph power Gc has clique-width at most 2kck.[13] Although there is an exponential gap in both the bound for clique-width from treewidth and the bound for clique-width of graph powers, these bounds do not compound each other: if a graph G has treewidth w, then Gc has clique-width at most 2(c + 1)w + 1 − 2, only singly exponential in the treewidth.[14]
Computational complexity
 | Unsolved problem in mathematics: Can graphs of bounded clique-width be recognized in polynomial time? (more unsolved problems in mathematics) |
Many optimization problems that are NP-hard for more general classes of graphs may be solved efficiently by dynamic programming on graphs of bounded clique-width, when a construction sequence for these graphs is known.[15][16] In particular, every graph property that can be expressed in MSO1 monadic second-order logic (a form of logic allowing quantification over sets of vertices) has a linear-time algorithm for graphs of bounded clique-width, by a form of Courcelle's theorem.[16] It is also possible to find optimal graph colorings or Hamiltonian cycles for graphs of bounded clique-width in polynomial time, when a construction sequence is known, but the exponent of the polynomial increases with the clique-width, and evidence from computational complexity theory shows that this dependence is likely to be necessary.[17]
The graphs of clique-width three can be recognized, and a construction sequence found for them, in polynomial time using an algorithm based on split decomposition.[18] For graphs of unbounded clique-width, it is NP-hard to compute the clique-width exactly, and also NP-hard to obtain an approximation with sublinear additive error.[19] However, when the clique-width is bounded, it is possible to obtain a construction sequence of bounded width (exponentially larger than the actual clique-width) in polynomial time.[20] It remains open whether the exact clique-width, or a tighter approximation to it, can be calculated in fixed-parameter tractable time, whether it can be calculated in polynomial time for every fixed bound on the clique-width, or even whether the graphs of clique-width four can be recognized in polynomial time.[19]
Relation to treewidth
The theory of graphs of bounded clique-width resembles that for graphs of bounded treewidth, but unlike treewidth allows for dense graphs. If a family of graphs has bounded clique-width, then either it has bounded treewidth or every complete bipartite graph is a subgraph of a graph in the family.[11] Treewidth and clique-width are also connected through the theory of line graphs: a family of graphs has bounded treewidth if and only if their line graphs have bounded clique-width.[21]
Notes
- ↑ Courcelle, Engelfriet & Rozenberg (1993).
- ↑ Courcelle (1993).
- ↑ Courcelle & Olariu (2000).
- ↑ Golumbic & Rotics (2000).
- ↑ Brandstädt & Lozin (2003).
- ↑ Brandstädt et al. (2005); Brandstädt et al. (2006).
- ↑ Brandstädt & Hundt (2008); Gurski & Wanke (2009).
- ↑ Courcelle & Olariu (2000), Corollary 3.3.
- ↑ Courcelle & Olariu (2000), Theorem 4.1.
- ↑ Corneil & Rotics (2005), strengthening Courcelle & Olariu (2000), Theorem 5.5.
- 1 2 Gurski & Wanke (2000).
- ↑ Oum & Seymour (2006).
- ↑ Todinca (2003).
- ↑ Gurski & Wanke (2009).
- ↑ Cogis & Thierry (2005).
- 1 2 Courcelle, Makowsky & Rotics (2000).
- ↑ Fomin et al. (2010).
- ↑ Corneil et al. (2012).
- 1 2 Fellows et al. (2009).
- ↑ Oum & Seymour (2006); Hliněný & Oum (2008); Oum (2009).
- ↑ Gurski & Wanke (2007).
References
- Brandstädt, A.; Dragan, F.F.; Le, H.-O.; Mosca, R. (2005), "New graph classes of bounded clique-width", Theory of Computing Systems, 38: 623–645, CiteSeerX 10.1.1.3.5994
, doi:10.1007/s00224-004-1154-6. - Brandstädt, A.; Engelfriet, J.; Le, H.-O.; Lozin, V.V. (2006), "Clique-width for 4-vertex forbidden subgraphs", Theory of Computing Systems, 39: 561–590, doi:10.1007/s00224-005-1199-1.
- Brandstädt, Andreas; Hundt, Christian (2008), "Ptolemaic graphs and interval graphs are leaf powers", LATIN 2008: Theoretical informatics, Lecture Notes in Comput. Sci., 4957, Springer, Berlin, pp. 479–491, MR 2472761, doi:10.1007/978-3-540-78773-0_42.
- Brandstädt, A.; Lozin, V.V. (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 sets for distance-hereditary graphs", Discrete Optimization, 2 (2): 185–188, MR 2155518, doi:10.1016/j.disopt.2005.03.004.
- Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi (2012), "Polynomial-time recognition of clique-width ≤ 3 graphs", Discrete Applied Mathematics, 160 (6): 834–865, MR 2901093, doi:10.1016/j.dam.2011.03.020.
- Corneil, Derek G.; Rotics, Udi (2005), "On the relationship between clique-width and treewidth", SIAM Journal on Computing, 34 (4): 825–847, MR 2148860, doi:10.1137/S0097539701385351.
- Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz (1993), "Handle-rewriting hypergraph grammars", Journal of Computer and System Sciences, 46 (2): 218–270, MR 1217156, doi:10.1016/0022-0000(93)90004-G. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), MR1431281.
- Courcelle, B. (1993), "Monadic second-order logic and hypergraph orientation", Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93), pp. 179–190, doi:10.1109/LICS.1993.287589.
- Courcelle, B.; Makowsky, J. A.; 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.
- Courcelle, B.; Olariu, S. (2000), "Upper bounds to the clique width of graphs", Discrete Applied Mathematics, 101 (1–3): 77–144, doi:10.1016/S0166-218X(99)00184-5.
- 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, MR 2519936, doi:10.1137/070687256.
- 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 , MR 2592039, doi:10.1137/080742270.
- 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, MR 1792124, doi:10.1142/S0129054100000260.
- Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without Kn,n", in Brandes, Ulrik; Wagner, Dorothea, Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science, 1928, Berlin: Springer, pp. 196–205, MR 1850348, doi:10.1007/3-540-40064-8_19.
- Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded 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 of bounded tree-width", Discrete Applied Mathematics, 157 (4): 583–595, MR 2499471, doi:10.1016/j.dam.2008.08.031.
- Hliněný, Petr; Oum, Sang-il (2008), "Finding branch-decompositions and rank-decompositions", SIAM Journal on Computing, 38 (3): 1012–1032, MR 2421076, doi:10.1137/070685920.
- Oum, Sang-il; Seymour, Paul (2006), "Approximating clique-width and branch-width", Journal of Combinatorial Theory, Series B, 96 (4): 514–528, MR 2232389, doi:10.1016/j.jctb.2005.10.006.
- Oum, Sang-il (2009), "Approximating rank-width and clique-width quickly", ACM Transactions on Algorithms, 5 (1): Art. 10, 20, CiteSeerX 10.1.1.574.8156 , MR 2479181, doi:10.1007/11604686_5.
- Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., 2880, Springer, Berlin, pp. 370–382, MR 2080095, doi:10.1007/978-3-540-39890-5_32.
- Wanke, Egon (1994), "k-NLC graphs and polynomial algorithms", Discrete Applied Mathematics, 54 (2-3): 251–266, MR 1300250, doi:10.1016/0166-218X(94)90026-4.