Clique-width

File:Clique-width construction.svg 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 {{mvar|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 {{mvar|G}} by means of the following 4 operations :

Creation of a new vertex {{mvar|v}} with label {{mvar|i}} (denoted by {{math|i(v)}})
Disjoint union of two labeled graphs {{mvar|G}} and {{mvar|H}} (denoted by $G \oplus H$ )
Joining by an edge every vertex labeled {{mvar|i}} to every vertex labeled {{mvar|j}} (denoted by {{math|η(i,j)}}), where {{math|i ≠ j}}
Renaming label {{mvar|i}} to label {{mvar|j}} (denoted by {{math|ρ(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{{sfnp|Courcelle|Engelfriet|Rozenberg|1993}} and by {{harvtxt|Wanke|1994}}. The name "clique-width" was used for a different concept by {{harvtxt|Chlebíková|1992}}. By 1993, the term already had its present meaning.{{sfnp|Courcelle|1993}}

Special classes of graphs

Cographs are exactly the graphs with clique-width at most 2.{{sfnp|Courcelle|Olariu|2000}}

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).{{sfnp|Golumbic|Rotics|2000}}

Similarly, the clique-width of bipartite permutation graphs is unbounded (based on similar grid structure).{{sfnp|Brandstädt|Lozin|2003}}

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.{{harvtxt|Brandstädt|Dragan|Le|Mosca|2005}}; {{harvtxt|Brandstädt|Engelfriet|Le|Lozin|2006}}.

Other graphs with bounded clique-width include the Leaf power for bounded values of {{mvar|k}}; these are the induced subgraphs of the leaves of a tree {{mvar|T}} in the graph power {{math|T^k}}. However, leaf powers with unbounded exponents do not have bounded clique-width.{{harvtxt|Brandstädt|Hundt|2008}}; {{harvtxt|Gurski|Wanke|2009}}.

Bounds

{{harvtxt|Courcelle|Olariu|2000}} and {{harvtxt|Corneil|Rotics|2005}} proved the following bounds on the clique-width of certain graphs:

If a graph has clique-width at most {{mvar|k}}, then so does every induced subgraph of the graph.{{harvtxt|Courcelle|Olariu|2000}}, Corollary 3.3.
The complement graph of a graph of clique-width {{mvar|k}} has clique-width at most {{math|2k}}.{{harvtxt|Courcelle|Olariu|2000}}, Theorem 4.1.
The graphs of treewidth {{mvar|w}} have clique-width at most {{math|3 · 2^{w − 1}}}. The exponential dependence in this bound is necessary: there exist graphs whose clique-width is exponentially larger than their treewidth.{{harvtxt|Corneil|Rotics|2005}}, strengthening {{harvtxt|Courcelle|Olariu|2000}}, Theorem 5.5. In the other direction, graphs of bounded clique-width can have unbounded treewidth; for instance, {{mvar|n}}-vertex complete graphs have clique-width 2 but treewidth {{math|n − 1}}. However, graphs of clique-width {{mvar|k}} that Biclique-free graph have treewidth at most {{math|3k(t − 1) − 1}}. Therefore, for every family of sparse graphs, having bounded treewidth is equivalent to having bounded clique-width.{{sfnp|Gurski|Wanke|2000}}
Another graph parameter, the rank-width, is bounded in both directions by the clique-width: {{nowrap|rank-width ≤ clique-width ≤ 2^{rank-width + 1}.{{sfnp|Oum|Seymour|2006}}}}

Additionally, if a graph {{mvar|G}} has clique-width {{mvar|k}}, then the graph power {{math|G^c}} has clique-width at most {{math|2kc^k}}.{{sfnp|Todinca|2003}} 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 {{mvar|G}} has treewidth {{mvar|w}}, then {{math|G^c}} has clique-width at most {{math|2(c + 1)^{w + 1} − 2}}, only singly exponential in the treewidth.{{sfnp|Gurski|Wanke|2009}}

Computational complexity

{{unsolved|mathematics|Can graphs of bounded clique-width be recognized in polynomial time?}}

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.{{sfnp|Cogis|Thierry|2005}}{{sfnp|Courcelle|Makowsky|Rotics|2000}} 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.{{sfnp|Courcelle|Makowsky|Rotics|2000}}

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.{{sfnp|Fomin|Golovach|Lokshtanov|Saurabh|2010}}

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.{{sfnp|Dvořák|Král'|2012}}

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.{{sfnp|Corneil|Habib|Lanlignel|Reed|2012}}

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.{{sfnp|Fellows|Rosamond|Rotics|Szeider|2009}} 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,{{harvtxt|Oum|Seymour|2006}}; {{harvtxt|Hliněný|Oum|2008}}; {{harvtxt|Oum|2008}}; {{harvtxt|Fomin|Korhonen|2022}}. in particular in quadratic time in the number of vertices.{{sfnp|Fomin|Korhonen|2022}} 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.{{sfnp|Fellows|Rosamond|Rotics|Szeider|2009}}

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.{{sfnp|Gurski|Wanke|2000}} 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.{{sfnp|Gurski|Wanke|2007}}

The graphs of bounded clique-width also have bounded twin-width.{{sfnp|Bonnet|Kim|Thomassé|Watrigant|2022}}

Notes

References

{{citation

| last1 = Bonnet | first1 = Édouard

| last2 = Kim | first2 = Eun Jung

| last3 = Thomassé | first3 = Stéphan

| last4 = Watrigant | first4 = Rémi

| arxiv = 2004.14789

| doi = 10.1145/3486655

| issue = 1

| journal = Journal of the ACM

| mr = 4402362

| page = A3:1–A3:46

| title = Twin-width I: Tractable FO model checking

| volume = 69

| year = 2022}}

{{citation

| last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt

| last2 = Dragan | first2 = F.F.

| last3 = Le | first3 = H.-O.

| last4 = Mosca | first4 = R.

| title = New graph classes of bounded clique-width

| journal = Theory of Computing Systems

| volume = 38 | year = 2005 | issue = 5 | pages = 623–645

| doi = 10.1007/s00224-004-1154-6

| citeseerx = 10.1.1.3.5994| s2cid = 2309695 }}.

{{citation

| last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt

| last2 = Engelfriet | first2 = J.

| last3 = Le | first3 = H.-O.

| last4 = Lozin | first4 = V.V.

| title = Clique-width for 4-vertex forbidden subgraphs

| journal = Theory of Computing Systems

| volume = 39 | year = 2006 | issue = 4 | pages = 561–590

| doi = 10.1007/s00224-005-1199-1

| s2cid = 20050455 }}.

{{citation

| last1 = Brandstädt | first1 = Andreas

| last2 = Hundt | first2 = Christian

| contribution = Ptolemaic graphs and interval graphs are leaf powers

| doi = 10.1007/978-3-540-78773-0_42

| mr = 2472761

| pages = 479–491

| publisher = Springer, Berlin

| series = Lecture Notes in Comput. Sci.

| title = LATIN 2008: Theoretical informatics

| volume = 4957

| year = 2008}}.

{{citation

| last1 = Brandstädt | first1 = A. | author1-link = Andreas Brandstädt

| last2 = Lozin | first2 = V.V.

| title = On the linear structure and clique-width of bipartite permutation graphs

| journal = Ars Combinatoria

| volume = 67 | year = 2003 | pages = 273–281

| citeseerx = 10.1.1.16.2000}}.

{{citation

| last = Chlebíková | first = J. | author-link = Janka Chlebíková

| issue = 2

| journal = Acta Mathematica Universitatis Comenianae

| mr = 1205875

| pages = 225–236

| series = New Series

| title = On the tree-width of a graph

| volume = 61

| year = 1992| citeseerx = 10.1.1.30.3900

}}.

{{citation

| last1 = Cogis | first1 = O.

| last2 = Thierry | first2 = E.

| title = Computing maximum stable sets for distance-hereditary graphs

| journal = Discrete Optimization

| volume = 2 | issue = 2 | year = 2005 | pages = 185–188

| mr = 2155518

| doi = 10.1016/j.disopt.2005.03.004| doi-access = free}}.

{{citation

| last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil

| last2 = Habib | first2 = Michel

| last3 = Lanlignel | first3 = Jean-Marc

| last4 = Reed | first4 = Bruce | author4-link = Bruce Reed (mathematician)

| last5 = Rotics | first5 = Udi

| doi = 10.1016/j.dam.2011.03.020

| issue = 6

| journal = Discrete Applied Mathematics

| mr = 2901093

| pages = 834–865

| title = Polynomial-time recognition of clique-width {{math|≤ 3}} graphs

| volume = 160

| year = 2012| doi-access = free

}}.

{{citation

| last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil

| last2 = Rotics | first2 = Udi

| doi = 10.1137/S0097539701385351

| issue = 4

| journal = SIAM Journal on Computing

| mr = 2148860

| pages = 825–847

| title = On the relationship between clique-width and treewidth

| volume = 34

| year = 2005}}.

{{citation

| last1 = Courcelle | first1 = Bruno | author1-link = Bruno Courcelle

| last2 = Engelfriet | first2 = Joost

| last3 = Rozenberg | first3 = Grzegorz

| doi = 10.1016/0022-0000(93)90004-G

| issue = 2

| journal = Journal of Computer and System Sciences

| mr = 1217156

| pages = 218–270

| title = Handle-rewriting hypergraph grammars

| volume = 46

| year = 1993| doi-access = free

}}. Presented in preliminary form in Graph grammars and their application to computer science (Bremen, 1990), {{MR|1431281}}.

{{citation

| last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle

| contribution = Monadic second-order logic and hypergraph orientation

| doi = 10.1109/LICS.1993.287589

| pages = 179–190

| title = Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93)

| year = 1993| s2cid = 39254668 }}.

{{citation

| last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle

| last2 = Makowsky | first2 = J. A. | author2-link = Johann Makowsky

| last3 = Rotics | first3 = U.

| title = Linear time solvable optimization problems on graphs on bounded clique width

| journal = Theory of Computing Systems

| volume = 33 | issue = 2 | year = 2000 | pages = 125–150

| doi = 10.1007/s002249910009| citeseerx = 10.1.1.414.1845| s2cid = 15402031 }}.

{{citation

| last1 = Courcelle | first1 = B. | author1-link = Bruno Courcelle

| last2 = Olariu | first2 = S.

| title = Upper bounds to the clique width of graphs

| journal = Discrete Applied Mathematics

| volume = 101 | issue = 1–3 | year = 2000 | pages = 77–144 | doi = 10.1016/S0166-218X(99)00184-5| url = https://digitalcommons.odu.edu/computerscience_fac_pubs/122 | doi-access = free }}.

{{citation

| last1 = Dvořák | first1 = Zdeněk

| last2 = Král' | first2 = Daniel

| arxiv = 1107.2161

| doi = 10.1016/j.ejc.2011.12.005

| issue = 4

| journal = Electronic Journal of Combinatorics

| pages = 679–683

| title = Classes of graphs with small rank decompositions are χ-bounded

| volume = 33

| year = 2012| s2cid = 5530520

}}

{{citation

| last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows

| last2 = Rosamond | first2 = Frances A. | author2-link = Frances A. Rosamond

| last3 = Rotics | first3 = Udi

| last4 = Szeider | first4 = Stefan | author4-link = Stefan Szeider

| doi = 10.1137/070687256

| issue = 2

| journal = SIAM Journal on Discrete Mathematics

| mr = 2519936

| pages = 909–939

| title = Clique-width is NP-complete

| volume = 23

| year = 2009}}.

{{citation

| last1 = Fomin | first1 = Fedor V.

| last2 = Golovach | first2 = Petr A.

| last3 = Lokshtanov | first3 = Daniel

| last4 = Saurabh | first4 = Saket

| doi = 10.1137/080742270

| issue = 5

| journal = SIAM Journal on Computing

| mr = 2592039

| pages = 1941–1956

| title = Intractability of clique-width parameterizations

| volume = 39

| year = 2010| citeseerx = 10.1.1.220.1712}}.

{{citation

| last1 = Fomin | first1 = Fedor V.

| last2 = Korhonen | first2 = Tuukka

| contribution = Fast FPT-approximation of branchwidth

| doi = 10.1145/3519935.3519996

| pages = 886–899

| publisher = ACM

| title = Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

| arxiv = 2111.03492

| year = 2022| s2cid = 243832882

}}.

{{citation

| last1 = Golumbic | first1 = Martin Charles | authorlink = Martin Charles Golumbic

| last2 = Rotics | first2 = Udi

| title = On the clique-width of some perfect graph classes

| journal = International Journal of Foundations of Computer Science

| volume = 11 | issue = 3 | year = 2000 | pages = 423–443

| mr = 1792124

| doi = 10.1142/S0129054100000260}}.

{{citation

| last1 = Gurski | first1 = Frank

| last2 = Wanke | first2 = Egon

| editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes

| editor2-last = Wagner | editor2-first = Dorothea | editor2-link = Dorothea Wagner

| contribution = The tree-width of clique-width bounded graphs without {{math|K_n,n}}

| doi = 10.1007/3-540-40064-8_19

| location = Berlin

| mr = 1850348

| pages = 196–205

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings

| volume = 1928

| year = 2000}}.

{{citation

| last1 = Gurski | first1 = Frank

| last2 = Wanke | first2 = Egon

| title = Line graphs of bounded clique-width

| journal = Discrete Mathematics

| volume = 307

| issue = 22

| year = 2007

| pages = 2734–2754

| doi = 10.1016/j.disc.2007.01.020| doi-access = free

}}.

{{citation

| last1 = Gurski | first1 = Frank

| last2 = Wanke | first2 = Egon

| doi = 10.1016/j.dam.2008.08.031

| issue = 4

| journal = Discrete Applied Mathematics

| mr = 2499471

| pages = 583–595

| title = The NLC-width and clique-width for powers of graphs of bounded tree-width

| volume = 157

| year = 2009| doi-access = free

}}.

{{citation

| last1 = Hliněný | first1 = Petr

| last2 = Oum | first2 = Sang-il |author-link2= Oum Sang-il

| doi = 10.1137/070685920

| issue = 3

| journal = SIAM Journal on Computing

| mr = 2421076

| pages = 1012–1032

| title = Finding branch-decompositions and rank-decompositions

| volume = 38

| year = 2008| citeseerx = 10.1.1.94.2272

}}.

{{citation

| last1 = Oum | first1 = Sang-il |author-link1= Oum Sang-il

| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)

| doi = 10.1016/j.jctb.2005.10.006

| issue = 4

| journal = Journal of Combinatorial Theory

| mr = 2232389

| pages = 514–528

| series = Series B

| title = Approximating clique-width and branch-width

| volume = 96

| year = 2006| doi-access = free

}}.

{{citation

| last = Oum | first = Sang-il |author-link= Oum Sang-il

| doi = 10.1145/1435375.1435385

| issue = 1

| journal = ACM Transactions on Algorithms

| mr = 2479181

| page = Art. 10, 20

| title = Approximating rank-width and clique-width quickly

| volume = 5

| year = 2008 | citeseerx = 10.1.1.574.8156

}}.

{{citation

| last = Todinca | first = Ioan

| contribution = Coloring powers of graphs of bounded clique-width

| doi = 10.1007/978-3-540-39890-5_32

| mr = 2080095

| pages = 370–382

| publisher = Springer, Berlin

| series = Lecture Notes in Comput. Sci.

| title = Graph-theoretic concepts in computer science

| volume = 2880

| year = 2003}}.

{{citation

| last = Wanke | first = Egon

| doi = 10.1016/0166-218X(94)90026-4

| issue = 2–3

| journal = Discrete Applied Mathematics

| mr = 1300250

| pages = 251–266

| title = {{mvar|k}}-NLC graphs and polynomial algorithms

| volume = 54

| year = 1994| doi-access = free

}}.

Category:Graph invariants