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 with label (denoted by )
#Disjoint union of two labeled graphs and (denoted by $G \oplus H$)
#Joining by an edge every vertex labeled to every vertex labeled (denoted by ), where
#Renaming label to label (denoted by )

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 -leaf powers for bounded values of ; these are the induced subgraphs of the leaves of a tree in the graph power . 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 , then so does every induced subgraph of the graph.
*The complement graph of a graph of clique-width has clique-width at most .
*The graphs of treewidth have clique-width at most . 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, -vertex complete graphs have clique-width 2 but treewidth . However, graphs of clique-width that have no complete bipartite graph as a subgraph have treewidth at most . 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 ≤ 2^{rank-width + 1}.

Additionally, if a graph has clique-width , then the graph power has clique-width at most . 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 has treewidth , then has clique-width at most , 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 MSO₁ 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

*
*.
*.
*.
*.
*.
*.
*.
*.
*. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), .
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
{{refend

Graph invariants