Clique-width

File:Clique-width construction.svg

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 Template:Mvar 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 Template:Mvar by means of the following 4 operations :

1. Creation of a new vertex Template:Mvar with label Template:Mvar (denoted by i(v))
2. Disjoint union of two labeled graphs Template:Mvar and Template:Mvar (denoted by $G\oplus H$)
3. Joining by an edge every vertex labeled Template:Mvar to every vertex labeled Template:Mvar (denoted by η(i,j)), where i ≠ j
4. Renaming label Template:Mvar to label Template:Mvar (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 1990Template:Sfnp and by . The name "clique-width" was used for a different concept by . By 1993, the term already had its present meaning.Template:Sfnp

Special classes of graphs

Cographs are exactly the graphs with clique-width at most 2.Template:Sfnp 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).Template:Sfnp Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure).Template:Sfnp 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 power|Template:Mvar-leaf powers]] for bounded values of Template:Mvar; these are the induced subgraphs of the leaves of a tree Template:Mvar 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 Template:Mvar, then so does every induced subgraph of the graph.
• The complement graph of a graph of clique-width Template:Mvar has clique-width at most 2k.
• The graphs of treewidth Template:Mvar have clique-width at most 3 · 2^{w − 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, Template:Mvar-vertex complete graphs have clique-width 2 but treewidth n − 1. However, graphs of clique-width Template:Mvar 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.Template:Sfnp
• Another graph parameter, the rank-width, is bounded in both directions by the clique-width: rank-width ≤ clique-width ≤ 2^{rank-width + 1}.Template:Sfnp

Additionally, if a graph Template:Mvar has clique-width Template:Mvar, then the graph power G^c has clique-width at most 2kc^k.Template:Sfnp 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 Template:Mvar has treewidth Template:Mvar, then G^c has clique-width at most 2(c + 1)^{w + 1} − 2, only singly exponential in the treewidth.Template:Sfnp

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.Template:SfnpTemplate:Sfnp 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.Template:Sfnp

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.Template:Sfnp The graphs of bounded clique-width are [[χ-bounded|Template:Mvar-bounded]], meaning that their chromatic number is at most a function of the size of their largest clique.Template:Sfnp

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.Template:Sfnp 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.Template:Sfnp 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.Template:Sfnp 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.Template:Sfnp

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.Template:Sfnp 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.Template:Sfnp

The graphs of bounded clique-width also have bounded twin-width.Template:Sfnp

References

• .
• .
• .
• .
• .
• .
• .
• .
• . Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), MRTemplate:Catalog lookup link.
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .