Clique-width

The clique width is a term from graph theory and assigns each undirected graph is a natural number to. Therefore, it is a graph of parameters. On graphs with bounded clique width, many NP- complete problems such as HAMILTON COUNTY or CLIQUE and the closely related INDEPENDENT QUANTITY can be solved in polynomial time.

Definition

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

K -labeled graph

  • Was for a
  • A k -labeled graph is a graph whose nodes are labeled with a label image
  • A graph with exactly one with labeled nodes is denoted by

Clique width

A labeled graph is a clique size of most, if included in the graph class. It is defined inductively as follows:

The clique width of a labeled graph is the smallest natural number and is denoted by.

An expression that results from the operations, and where, is composed is called a clique width k- expression or k- expression.

Example

The undirected graph with 6 nodes has a clique of size 3, since it can be generated with the following operations:

The corresponding expression is

The right is the corresponding 3- expression tree for mapped.

Clique width special graph classes

Although determining the clique width of graphs in general is NP-complete, can the clique width of graphs to estimate certain special properties, at least to the top. There exist the following relationships:

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

Furthermore, it is known that co- graph have a clique size of at most 2, and that each graph with a gang size of more than 2 is a co- graph.

Relationship between clique width and tree-width

There are several relationships between the clique width and the tree-width of an undirected graph.

The following statement shows that it is possible to estimate through to the top:

Conversely it can be the tree-width of a graph is generally not limited by his clique width, as one can easily consider the example of complete graphs is:

The complete graph with node has a tree-width of clique and a width of not more than 2 thus applies to all with:

But it is possible, under certain circumstances, the tree-width by the clique width estimate upwards.

Does not have a complete bipartite graph as a subgraph, then the following statement applies:

Relationship between clique width and NLC- width

The clique width can be estimated both downward and upward through the NLC- width:

Clique problem Co-Graph Treewidth
194539
de