Definition
Clique-width is a graph invariant that measures the structural complexity of a finite undirected graph. Formally, the clique‑width of a graph $G$ is the minimum number of labels required to construct $G$ using the following four operations:
- Creation of a new vertex with a given label.
- Disjoint union of two labeled graphs.
- Joining all vertices with label $i$ to all vertices with label $j$ (for $i eq j$).
- Relabeling all vertices of label $i$ to label $j$.
A graph that can be generated with at most $k$ labels has clique‑width at most $k$.
Overview
Clique‑width was introduced as a means to extend algorithmic results that were previously limited to graphs of bounded treewidth. While many computational problems remain NP‑hard on general graphs, they become tractable (often solvable in linear or polynomial time) on classes of graphs with bounded clique‑width when the construction expression (called a k‑expression) is given. The parameter is especially useful for dense graph classes where treewidth is unbounded, such as cographs, complete bipartite graphs, and graphs of bounded rank‑width.
The concept has motivated a substantial body of research in graph theory and algorithm design, focusing on the identification of graph classes with bounded clique‑width, the development of efficient algorithms for computing or approximating clique‑width, and the exploration of its connections to other width parameters.
Etymology/Origin
The term “clique‑width” originates from the observation that the operation of joining all vertices of one label to all vertices of another creates a complete bipartite subgraph (a clique in the complementary sense). The parameter was formally defined in the late 1990s by Bruno Courcelle, Joost Engelfriet, and their collaborators. A seminal paper, Courcelle and Olariu “Upper bounds to the clique‑width of graphs” (2000), gave the name and established early results regarding its relationship with other width measures.
Characteristics
| Property | Description |
|---|---|
| Label‑based construction | Uses a finite set of labels and four primitive operations to build the graph. |
| Boundedness | A graph class has bounded clique‑width if there exists a constant $k$ such that every graph in the class has clique‑width ≤ $k$. |
| Relation to treewidth | Every graph of treewidth $t$ has clique‑width at most $2^{t+1}-1$. Conversely, bounded clique‑width does not imply bounded treewidth; many dense graphs have low clique‑width but unbounded treewidth. |
| Algorithmic implications | Many MSO$_1$ (Monadic Second‑Order) definable problems are solvable in linear time on graphs of bounded clique‑width when a k‑expression is provided (Courcelle’s theorem for MSO$_1$). |
| Computational difficulty | Determining the exact clique‑width of a graph is NP‑complete. Approximation within any constant factor is also NP‑hard, though fixed‑parameter algorithms exist for specific graph classes. |
| Related parameters | Rank‑width and NLC‑width are closely related; rank‑width is within a constant factor of clique‑width, and bounded rank‑width implies bounded clique‑width and vice versa. |
| Closure properties | The class of graphs with clique‑width ≤ $k$ is closed under taking induced subgraphs, disjoint union, and graph complementation. |
Related Topics
- Treewidth – another width parameter based on tree decompositions; often compared with clique‑width.
- Rank‑width – a width measure defined via rank functions on adjacency matrices; closely linked to clique‑width.
- NLC‑width – a variant of clique‑width based on node‑label controlled graph grammars.
- Graph minors – the theory of graph minors underlies many results about treewidth; clique‑width behaves differently with respect to minors.
- Courcelle’s theorem – expresses the tractability of MSO logic on graphs of bounded treewidth and, in a variant, bounded clique‑width.
- Graph classes of bounded clique‑width – examples include cographs, distance‑hereditary graphs, and graphs of bounded rank‑width.
References (representative works):
- Courcelle, B., & Olariu, S. (2000). Upper bounds to the clique‑width of graphs. Discrete Applied Mathematics, 101(1‑3), 77‑114.
- Oum, S., & Seymour, P. (2006). Approximating clique‑width and branch‑width. Journal of Combinatorial Theory, Series B, 96(4), 514‑528.
- Gurski, F., & Wanke, E. (2000). The linear time solution of NP‑complete problems on graphs of bounded clique‑width. Discrete Applied Mathematics, 108(1‑2), 215‑228.