Clique width

The clique width is a term from graph theory and assigns a natural number to every undirected graph . It is therefore a graph parameter . With the help of a k-expression (see below) many NP-complete problems such as HAMILTONKREIS or CLIQUE and the closely related INDEPENDENT QUANTITY in time can be solved, which is a linear running time for constant . However, since it is not known whether a k-expression can be calculated sufficiently quickly, it is currently unclear whether one can conclude from this that these problems can be efficiently solved on graphs with a limited clique size. ${\displaystyle G=(V,E)}$ ${\displaystyle O(f(k)\cdot n)}$ ${\displaystyle k}$

definition

The concept of the clique size of a graph was first introduced by Bruno Courcelle and Stephan Olariu. For the definition of the clique width, the concept of the k-marked graph must first be introduced:

k-marked graph

• For one be ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle \lbrack k\rbrack :=\lbrace 1,\ldots ,k\rbrace }$
• A k-marked graph is a graph whose nodes are marked with a marker image ${\displaystyle \ G=(V_{G},E_{G},lab_{G})\ }$ ${\displaystyle \ (V_{G},E_{G})\ }$ ${\displaystyle lab_{G}:V_{G}\rightarrow \lbrack k\rbrack }$
• A graph with exactly one node marked with is denoted by ${\displaystyle i\in \lbrack k\rbrack }$ ${\displaystyle \bullet _{i}}$

Clique width

A -marked graph has a clique width of at most if is contained in the graph class . It is inductively defined as follows: ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle CW_{k}}$ ${\displaystyle CW_{k}}$

1. The -marked graph (a graph consisting of a node with a marking ) is in for everyone ${\displaystyle k}$ ${\displaystyle \bullet _{i}}$ ${\displaystyle i}$ ${\displaystyle CW_{k}}$ ${\displaystyle i=1..k}$
2. Let and be node- disjoint -marked graphs. Then their disjoint union is in , with ${\displaystyle G=(V_{G},E_{G},lab_{G})}$ ${\displaystyle J=(V_{J},E_{J},lab_{J})}$ ${\displaystyle k}$ ${\displaystyle G\oplus J=(V',E',lab')}$ ${\displaystyle CW_{k}}$
   1. ${\displaystyle V':=V_{G}\cup V_{J}}$
   2. ${\displaystyle E':=E_{G}\cup E_{J}}$
   3. ${\displaystyle lab'(u)={\begin{cases}lab_{G}(u),&{\text{falls }}u\in V_{G},\\lab_{J}(u),&{\text{falls }}u\in V_{J}\end{cases}}}$    ${\displaystyle \forall u\in V'}$
3. Let a graph marked with and . There are ${\displaystyle i,j\in \lbrack k\rbrack }$ ${\displaystyle i\neq j}$ ${\displaystyle G=(V_{G},E_{G},lab_{G})}$ ${\displaystyle k}$
   1. of -labeled graph is obtained from G by marking all with marked nodes by a mark with is replaced in with ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \rho _{i\rightarrow j}(G)=(V_{G},E_{G},lab')}$ ${\displaystyle CW_{k}}$ ${\displaystyle lab'(u)={\begin{cases}lab_{G}(u),&{\text{falls }}lab_{G}(u)\neq i,\\j,&{\text{falls }}lab_{G}(u)=i\end{cases}}}$    ${\displaystyle \forall u\in V'}$
   2. the -marked graph, which results from G by connecting all nodes marked with with all nodes marked with. in with ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \eta _{i,j}(G)=(V_{G},E',lab_{G})}$ ${\displaystyle CW_{k}}$ ${\displaystyle E'=E_{G}\cup \lbrace \lbrace u,v\rbrace |lab(u)=i,lab(v)=j\rbrace }$

The clique width of a marked graph is the smallest natural number with and is denoted by. ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G\in CW_{k}}$ ${\displaystyle cw(G)}$

An expression which results from the operations , , and , wherein , composed is called clique-width-k expression or k-expression , respectively. ${\displaystyle X}$ ${\displaystyle \bullet _{i}}$ ${\displaystyle \oplus }$ ${\displaystyle \rho _{i\rightarrow j}}$ ${\displaystyle \eta _{i,j}}$ ${\displaystyle i,j\in \lbrack k\rbrack }$

example

The undirected graph with 6 nodes has a clique width of 3, since it can be generated with the following operations: ${\displaystyle C_{6}}$

3 expression tree for constructing the ${\displaystyle C_{6}}$

Clique-wide operation	Visualization of the graph
${\displaystyle G_{1}=\bullet _{1}}$
${\displaystyle G_{2}=\bullet _{2}}$
${\displaystyle G_{3}=G_{1}\oplus G_{2}}$
${\displaystyle G_{4}=\eta _{1,2}(G_{3})}$
${\displaystyle G_{5}=G_{4}\oplus G_{4}}$
${\displaystyle G_{6}=G_{5}\oplus \bullet _{3}}$
${\displaystyle G_{7}=\eta _{1,3}(G_{6})}$
${\displaystyle G_{8}=\rho _{3\rightarrow 1}(G_{7})}$
${\displaystyle G_{9}=G_{8}\oplus \bullet _{3}}$
${\displaystyle C_{6}=\eta _{2,3}(G_{9})}$

The associated expression is ${\displaystyle 3}$

${\displaystyle X=\eta _{2,3}(\rho _{3\rightarrow 1}(\eta _{1,3}(\eta (\bullet _{1}\oplus \bullet _{2})\oplus \eta (\bullet _{1}\oplus \bullet _{2})\oplus \bullet _{3}))\oplus \bullet _{3})}$

The corresponding 3-expression tree for is shown on the right. ${\displaystyle X}$

Clique width of special graph classes

Although the determination of the clique size of a graph is generally NP-complete , the clique size of certain graphs with special properties can at least be estimated upwards. The following relationships exist:

• Every complete graph has a clique size of at most 2
• Each path has a clique width of at most 3
• Even trees and distance preserving graph have a clique-width of at most 3

It is also known that co-graphs have a clique size of at most 2 and that every graph with a clique size of at most 2 is a co-graph.

Relationship between clique size and tree size

There are several relationships between the clique width and the tree width of an undirected graph . ${\displaystyle cw(G)}$ ${\displaystyle tw(G)}$ ${\displaystyle G}$

The following statement shows that through can be estimated up: ${\displaystyle cw(G)}$ ${\displaystyle tw(G)}$

${\displaystyle cw(G)\leq 3\cdot 2^{tw(G)-1}}$

Conversely, however, the tree width of a graph cannot generally be limited by its clique width, as can be easily seen using the example of complete graphs:

The complete graph with nodes has a tree width of and a clique width of at most 2. Thus, for all with : ${\displaystyle K_{n}}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n\geq 4}$

${\displaystyle cw(K_{n})<tw(K_{n})}$.

However, under certain circumstances the tree width can also be estimated by the clique width upwards.

If it does not have a completely bipartite graph as a subgraph , the following statement applies: ${\displaystyle G}$ ${\displaystyle K_{n,n}}$

${\displaystyle tw(G)\leq 3\cdot (n-1)\cdot cw(G)-1}$

Relationship between clique size and NLC size

The clique width can be estimated both downwards and upwards using the NLC width : ${\displaystyle nlcw(G)}$

${\displaystyle nlcw(G)\leq cw(G)\leq 2\cdot nlcw(G)}$

Individual evidence

1. ↑ Bruno Courcelle, Stephan Olariu: Upper bounds to the clique width of graphs , Discrete Applied Mathematics 101 (1-3): 77-144, 2000, doi : 10.1016 / S0166-218X (99) 00184-5
2. ↑ Derek Corneil, Udi Rotics: On the Relationship between Clique-Width and Treewidth , Lecture Notes in Computer Science, 2001, Volume 2204/2001, 78–90, doi : 10.1007 / 3-540-45477-2_9
3. ↑ Frank Gurski, Egon Wanke: The Tree-Width of Clique-Width Bounded Graphs without ${\displaystyle K_{n,n}}$ , Lecture Notes in Computer Science, 2000, Volume 1928/2000, 221–232, doi : 10.1007 / 3-540-40064-8_19

literature

• Bruno Courcelle, Stephan Olariu: Upper bounds to the clique width of graphs , Discrete Applied Mathematics 101 (1-3): 77-144, 2000, doi: 10.1016 / S0166-218X (99) 00184-5
• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exact algorithms for difficult graph problems , Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1
• Jörg Rothe: Complexity Theory and Cryptology , Springer-Verlag, Berlin Heidelberg, 2008, ISBN 978-3-540-79744-9