From Surf Wiki (app.surf) — the open knowledge base
Clique-width
Measure of graph complexity
Measure of graph complexity
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 :
- Creation of a new vertex v with label i (denoted by i(v))
- Disjoint union of two labeled graphs G and H (denoted by G \oplus H)
- Joining by an edge every vertex labeled i to every vertex labeled j (denoted by η(i,j)), where i ≠ j
- 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.
Notes
References
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation | editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes | editor2-last = Wagner | editor2-first = Dorothea | editor2-link = Dorothea Wagner
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
- {{citation
References
- {{harvtxt. Brandstädt. Dragan. Le. Mosca. 2005; {{harvtxt. Brandstädt. Engelfriet. Le. Lozin. 2006.
- {{harvtxt. Brandstädt. Hundt. 2008; {{harvtxt. Gurski. Wanke. 2009.
- {{harvtxt. Courcelle. Olariu. 2000, Corollary 3.3.
- {{harvtxt. Courcelle. Olariu. 2000, Theorem 4.1.
- {{harvtxt. Corneil. Rotics. 2005, strengthening {{harvtxt. Courcelle. Olariu. 2000, Theorem 5.5.
- {{harvtxt. Oum. Seymour. 2006; {{harvtxt. Hliněný. Oum. 2008; {{harvtxt. Oum. 2008; {{harvtxt. Fomin. Korhonen. 2022.
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.
Ask Mako anything about Clique-width — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report