Clique-width

Quality 0.50 · 2 views · Updated 2 months ago

Measure of graph complexity

title: "Clique-width" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-invariants"] description: "Measure of graph complexity" topic_path: "general/graph-invariants" source: "https://en.wikipedia.org/wiki/Clique-width" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Measure of graph complexity ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/4/43/Clique-width_construction.svg" caption="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 G \oplus H)
  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 and by . The name "clique-width" was used for a different concept by . By 1993, the term already had its present meaning.

Special classes of graphs

Cographs are exactly the graphs with clique-width at most 2. 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). Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure). 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.

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 T**k. However, leaf powers with unbounded exponents do not have bounded clique-width.

Bounds

and 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.
  • The complement graph of a graph of clique-width k has clique-width at most 2k.
  • 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. 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 K**t,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.
  • Another graph parameter, the rank-width, is bounded in both directions by the clique-width: rank-width ≤ clique-width ≤ 2rank-width + 1.

Additionally, if a graph G has clique-width k, then the graph power Gc has clique-width at most 2kc**k. 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.

Computational complexity

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. 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.

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. 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.

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. 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. 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, in particular in quadratic time in the number of vertices. 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.

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. 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.

The graphs of bounded clique-width also have bounded twin-width.

Notes

References

  • {{citation | last1 = Bonnet | first1 = Édouard | last2 = Kim | first2 = Eun Jung | last3 = Thomassé | first3 = Stéphan | last4 = Watrigant | first4 = Rémi | arxiv = 2004.14789 | doi = 10.1145/3486655 | issue = 1 | journal = Journal of the ACM | mr = 4402362 | page = A3:1–A3:46 | title = Twin-width I: Tractable FO model checking | volume = 69 | year = 2022}}
  • {{citation | last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt | last2 = Dragan | first2 = F.F. | last3 = Le | first3 = H.-O. | last4 = Mosca | first4 = R. | title = New graph classes of bounded clique-width | journal = Theory of Computing Systems | volume = 38 | year = 2005 | issue = 5 | pages = 623–645 | doi = 10.1007/s00224-004-1154-6 | citeseerx = 10.1.1.3.5994| s2cid = 2309695 }}.
  • {{citation | last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt | last2 = Engelfriet | first2 = J. | last3 = Le | first3 = H.-O. | last4 = Lozin | first4 = V.V. | title = Clique-width for 4-vertex forbidden subgraphs | journal = Theory of Computing Systems | volume = 39 | year = 2006 | issue = 4 | pages = 561–590 | doi = 10.1007/s00224-005-1199-1 | s2cid = 20050455 }}.
  • {{citation | last1 = Brandstädt | first1 = Andreas | last2 = Hundt | first2 = Christian | contribution = Ptolemaic graphs and interval graphs are leaf powers | doi = 10.1007/978-3-540-78773-0_42 | mr = 2472761 | pages = 479–491 | publisher = Springer, Berlin | series = Lecture Notes in Comput. Sci. | title = LATIN 2008: Theoretical informatics | volume = 4957 | year = 2008}}.
  • {{citation | last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt | last2 = Lozin | first2 = V.V. | title = On the linear structure and clique-width of bipartite permutation graphs | journal = Ars Combinatoria | volume = 67 | year = 2003 | pages = 273–281 | citeseerx = 10.1.1.16.2000}}.
  • {{citation | last = Chlebíková | first = J. | author-link = Janka Chlebíková | issue = 2 | journal = Acta Mathematica Universitatis Comenianae | mr = 1205875 | pages = 225–236 | series = New Series | title = On the tree-width of a graph | volume = 61 | year = 1992| citeseerx = 10.1.1.30.3900
  • {{citation | last1 = Cogis | first1 = O. | last2 = Thierry | first2 = E. | title = Computing maximum stable sets for distance-hereditary graphs | journal = Discrete Optimization | volume = 2 | issue = 2 | year = 2005 | pages = 185–188 | mr = 2155518 | doi = 10.1016/j.disopt.2005.03.004| doi-access = free}}.
  • {{citation | last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil | last2 = Habib | first2 = Michel | last3 = Lanlignel | first3 = Jean-Marc | last4 = Reed | first4 = Bruce | author4-link = Bruce Reed (mathematician) | last5 = Rotics | first5 = Udi | doi = 10.1016/j.dam.2011.03.020 | issue = 6 | journal = Discrete Applied Mathematics | mr = 2901093 | pages = 834–865 | title = Polynomial-time recognition of clique-width ≤ 3 graphs | volume = 160 | year = 2012| doi-access = free
  • {{citation | last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil | last2 = Rotics | first2 = Udi | doi = 10.1137/S0097539701385351 | issue = 4 | journal = SIAM Journal on Computing | mr = 2148860 | pages = 825–847 | title = On the relationship between clique-width and treewidth | volume = 34 | year = 2005}}.
  • {{citation | last1 = Courcelle | first1 = Bruno | author1-link = Bruno Courcelle | last2 = Engelfriet | first2 = Joost | last3 = Rozenberg | first3 = Grzegorz | doi = 10.1016/0022-0000(93)90004-G | issue = 2 | journal = Journal of Computer and System Sciences | mr = 1217156 | pages = 218–270 | title = Handle-rewriting hypergraph grammars | volume = 46 | year = 1993| doi-access = free
  • {{citation | last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle | contribution = Monadic second-order logic and hypergraph orientation | doi = 10.1109/LICS.1993.287589 | pages = 179–190 | title = Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93) | year = 1993| s2cid = 39254668 }}.
  • {{citation | last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle | last2 = Makowsky | first2 = J. A. | author2-link = Johann Makowsky | last3 = Rotics | first3 = U. | title = Linear time solvable optimization problems on graphs on bounded clique width | journal = Theory of Computing Systems | volume = 33 | issue = 2 | year = 2000 | pages = 125–150 | doi = 10.1007/s002249910009| citeseerx = 10.1.1.414.1845| s2cid = 15402031 }}.
  • {{citation | last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle | last2 = Olariu | first2 = S. | title = Upper bounds to the clique width of graphs | journal = Discrete Applied Mathematics | volume = 101 | issue = 1–3 | year = 2000 | pages = 77–144 | doi = 10.1016/S0166-218X(99)00184-5| url = https://digitalcommons.odu.edu/computerscience_fac_pubs/122 | doi-access = free }}.
  • {{citation | last1 = Dvořák | first1 = Zdeněk | last2 = Král' | first2 = Daniel | arxiv = 1107.2161 | doi = 10.1016/j.ejc.2011.12.005 | issue = 4 | journal = Electronic Journal of Combinatorics | pages = 679–683 | title = Classes of graphs with small rank decompositions are χ-bounded | volume = 33 | year = 2012| s2cid = 5530520
  • {{citation | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows | last2 = Rosamond | first2 = Frances A. | author2-link = Frances A. Rosamond | last3 = Rotics | first3 = Udi | last4 = Szeider | first4 = Stefan | author4-link = Stefan Szeider | doi = 10.1137/070687256 | issue = 2 | journal = SIAM Journal on Discrete Mathematics | mr = 2519936 | pages = 909–939 | title = Clique-width is NP-complete | volume = 23 | year = 2009}}.
  • {{citation | last1 = Fomin | first1 = Fedor V. | last2 = Golovach | first2 = Petr A. | last3 = Lokshtanov | first3 = Daniel | last4 = Saurabh | first4 = Saket | doi = 10.1137/080742270 | issue = 5 | journal = SIAM Journal on Computing | mr = 2592039 | pages = 1941–1956 | title = Intractability of clique-width parameterizations | volume = 39 | year = 2010| citeseerx = 10.1.1.220.1712}}.
  • {{citation | last1 = Fomin | first1 = Fedor V. | last2 = Korhonen | first2 = Tuukka | contribution = Fast FPT-approximation of branchwidth | doi = 10.1145/3519935.3519996 | pages = 886–899 | publisher = ACM | title = Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | arxiv = 2111.03492 | year = 2022| s2cid = 243832882
  • {{citation | last1 = Golumbic | first1 = Martin Charles | authorlink = Martin Charles Golumbic | last2 = Rotics | first2 = Udi | title = On the clique-width of some perfect graph classes | journal = International Journal of Foundations of Computer Science | volume = 11 | issue = 3 | year = 2000 | pages = 423–443 | mr = 1792124 | doi = 10.1142/S0129054100000260}}.
  • {{citation | last1 = Gurski | first1 = Frank | last2 = Wanke | first2 = Egon | editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes | editor2-last = Wagner | editor2-first = Dorothea | editor2-link = Dorothea Wagner | contribution = The tree-width of clique-width bounded graphs without Kn,n | doi = 10.1007/3-540-40064-8_19 | location = Berlin | mr = 1850348 | pages = 196–205 | publisher = Springer | series = Lecture Notes in Computer Science | title = Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings | volume = 1928 | year = 2000}}.
  • {{citation | last1 = Gurski | first1 = Frank | last2 = Wanke | first2 = Egon | title = Line graphs of bounded clique-width | journal = Discrete Mathematics | volume = 307 | issue = 22 | year = 2007 | pages = 2734–2754 | doi = 10.1016/j.disc.2007.01.020| doi-access = free
  • {{citation | last1 = Gurski | first1 = Frank | last2 = Wanke | first2 = Egon | doi = 10.1016/j.dam.2008.08.031 | issue = 4 | journal = Discrete Applied Mathematics | mr = 2499471 | pages = 583–595 | title = The NLC-width and clique-width for powers of graphs of bounded tree-width | volume = 157 | year = 2009| doi-access = free
  • {{citation | last1 = Hliněný | first1 = Petr | last2 = Oum | first2 = Sang-il |author-link2= Oum Sang-il | doi = 10.1137/070685920 | issue = 3 | journal = SIAM Journal on Computing | mr = 2421076 | pages = 1012–1032 | title = Finding branch-decompositions and rank-decompositions | volume = 38 | year = 2008| citeseerx = 10.1.1.94.2272
  • {{citation | last1 = Oum | first1 = Sang-il |author-link1= Oum Sang-il | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | doi = 10.1016/j.jctb.2005.10.006 | issue = 4 | journal = Journal of Combinatorial Theory | mr = 2232389 | pages = 514–528 | series = Series B | title = Approximating clique-width and branch-width | volume = 96 | year = 2006| doi-access = free
  • {{citation | last = Oum | first = Sang-il |author-link= Oum Sang-il | doi = 10.1145/1435375.1435385 | issue = 1 | journal = ACM Transactions on Algorithms | mr = 2479181 | page = Art. 10, 20 | title = Approximating rank-width and clique-width quickly | volume = 5 | year = 2008 | citeseerx = 10.1.1.574.8156
  • {{citation | last = Todinca | first = Ioan | contribution = Coloring powers of graphs of bounded clique-width | doi = 10.1007/978-3-540-39890-5_32 | mr = 2080095 | pages = 370–382 | publisher = Springer, Berlin | series = Lecture Notes in Comput. Sci. | title = Graph-theoretic concepts in computer science | volume = 2880 | year = 2003}}.
  • {{citation | last = Wanke | first = Egon | doi = 10.1016/0166-218X(94)90026-4 | issue = 2–3 | journal = Discrete Applied Mathematics | mr = 1300250 | pages = 251–266 | title = k-NLC graphs and polynomial algorithms | volume = 54 | year = 1994| doi-access = free

References

  1. {{harvtxt. Brandstädt. Dragan. Le. Mosca. 2005; {{harvtxt. Brandstädt. Engelfriet. Le. Lozin. 2006.
  2. {{harvtxt. Brandstädt. Hundt. 2008; {{harvtxt. Gurski. Wanke. 2009.
  3. {{harvtxt. Courcelle. Olariu. 2000, Corollary 3.3.
  4. {{harvtxt. Courcelle. Olariu. 2000, Theorem 4.1.
  5. {{harvtxt. Corneil. Rotics. 2005, strengthening {{harvtxt. Courcelle. Olariu. 2000, Theorem 5.5.
  6. {{harvtxt. Oum. Seymour. 2006; {{harvtxt. Hliněný. Oum. 2008; {{harvtxt. Oum. 2008; {{harvtxt. Fomin. Korhonen. 2022.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

graph-invariants