Clique-width

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 ${\displaystyle 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^[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]