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: