Clique-width

From HandWiki
Short description: Measure of graph complexity
Construction of a distance-hereditary graph of clique-width 3 by disjoint unions, relabelings, and label-joins. Vertex labels are shown as colors.

In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct G by means of the following 4 operations :

  1. Creation of a new vertex v with label i (denoted by i(v))
  2. Disjoint union of two labeled graphs G and H (denoted by [math]\displaystyle{ G \oplus H }[/math])
  3. Joining by an edge every vertex labeled i to every vertex labeled j (denoted by η(i,j)), where i ≠ j
  4. Renaming label i to label j (denoted by ρ(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 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 with no induced subgraph isomorphic to a 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) and (Corneil Rotics) 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

Question, Web Fundamentals.svg 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 bounded clique-width are χ-bounded, meaning that their chromatic number is at most a function of the size of their largest clique.[18]

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.[19] 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.[20] 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,[21] in particular in quadratic time in the number of vertices.[22] 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.[20]

Related width parameters

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.[23]

The graphs of bounded clique-width also have bounded twin-width.[24]

Notes

  1. ↑ Courcelle, Engelfriet & Rozenberg (1993).
  2. ↑ Courcelle (1993).
  3. ↑ Courcelle & Olariu (2000).
  4. ↑ Golumbic & Rotics (2000).
  5. ↑ Brandstädt & Lozin (2003).
  6. ↑ (Brandstädt Dragan); (Brandstädt Engelfriet).
  7. ↑ (Brandstädt Hundt); (Gurski Wanke).
  8. ↑ (Courcelle Olariu), Corollary 3.3.
  9. ↑ (Courcelle Olariu), Theorem 4.1.
  10. ↑ (Corneil Rotics), strengthening (Courcelle Olariu), Theorem 5.5.
  11. ↑ 11.0 11.1 Gurski & Wanke (2000).
  12. ↑ Oum & Seymour (2006).
  13. ↑ Todinca (2003).
  14. ↑ Gurski & Wanke (2009).
  15. ↑ Cogis & Thierry (2005).
  16. ↑ 16.0 16.1 Courcelle, Makowsky & Rotics (2000).
  17. ↑ Fomin et al. (2010).
  18. ↑ Dvořák & Král' (2012).
  19. ↑ Corneil et al. (2012).
  20. ↑ 20.0 20.1 Fellows et al. (2009).
  21. ↑ (Oum Seymour); (Hliněný Oum); (Oum 2008); (Fomin Korhonen).
  22. ↑ Fomin & Korhonen (2022).
  23. ↑ Gurski & Wanke (2007).
  24. ↑ Bonnet et al. (2022).

References

  • Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width I: Tractable FO model checking", Journal of the ACM 69 (1): A3:1–A3:46, doi:10.1145/3486655 
  • "New graph classes of bounded clique-width", Theory of Computing Systems 38 (5): 623–645, 2005, doi:10.1007/s00224-004-1154-6 .
  • "Clique-width for 4-vertex forbidden subgraphs", Theory of Computing Systems 39 (4): 561–590, 2006, 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, doi:10.1007/978-3-540-78773-0_42 .
  • "On the linear structure and clique-width of bipartite permutation graphs", Ars Combinatoria 67: 273–281, 2003 .
  • "On the tree-width of a graph", Acta Mathematica Universitatis Comenianae, New Series 61 (2): 225–236, 1992 .
  • Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", Discrete Optimization 2 (2): 185–188, doi:10.1016/j.disopt.2005.03.004 .
  • "Polynomial-time recognition of clique-width ≤ 3 graphs", Discrete Applied Mathematics 160 (6): 834–865, 2012, doi:10.1016/j.dam.2011.03.020 .
  • "On the relationship between clique-width and treewidth", SIAM Journal on Computing 34 (4): 825–847, 2005, doi:10.1137/S0097539701385351 .
  • "Handle-rewriting hypergraph grammars", Journal of Computer and System Sciences 46 (2): 218–270, 1993, doi:10.1016/0022-0000(93)90004-G . Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), MR1431281.
  • "Monadic second-order logic and hypergraph orientation", Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93), 1993, pp. 179–190, doi:10.1109/LICS.1993.287589 .
  • "Linear time solvable optimization problems on graphs on bounded clique width", Theory of Computing Systems 33 (2): 125–150, 2000, doi:10.1007/s002249910009 .
  • "Upper bounds to the clique width of graphs", Discrete Applied Mathematics 101 (1–3): 77–144, 2000, doi:10.1016/S0166-218X(99)00184-5, https://digitalcommons.odu.edu/computerscience_fac_pubs/122 .
  • Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank decompositions are χ-bounded", Electronic Journal of Combinatorics 33 (4): 679–683, doi:10.1016/j.ejc.2011.12.005 
  • "Clique-width is NP-complete", SIAM Journal on Discrete Mathematics 23 (2): 909–939, 2009, 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, doi:10.1137/080742270 .
  • Fomin, Fedor V.; Korhonen, Tuukka (2022), "Fast FPT-approximation of branchwidth", Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, pp. 886–899, doi:10.1145/3519935.3519996 .
  • "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science 11 (3): 423–443, 2000, doi:10.1142/S0129054100000260 .
  • Gurski, Frank; Wanke, Egon (2000), "The tree-width of clique-width bounded graphs without Kn,n", 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, 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, doi:10.1016/j.dam.2008.08.031 .
  • Hliněný, Petr (2008), "Finding branch-decompositions and rank-decompositions", SIAM Journal on Computing 38 (3): 1012–1032, doi:10.1137/070685920 .
  • "Approximating clique-width and branch-width", Journal of Combinatorial Theory, Series B 96 (4): 514–528, 2006, doi:10.1016/j.jctb.2005.10.006 .
  • "Approximating rank-width and clique-width quickly", ACM Transactions on Algorithms 5 (1): Art. 10, 20, 2008, doi:10.1145/1435375.1435385 .
  • 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, 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, doi:10.1016/0166-218X(94)90026-4 .



Retrieved from "https://handwiki.org/wiki/index.php?title=Clique-width&oldid=3360294"