Co-graph
In computer science , a co-graph is an undirected graph that can be constructed with certain elementary operations. Many difficult problems such as: B. solve CLIQUE and the closely related INDEPENDENT QUANTITY as well as NODE COVERAGE in linear time.
definition
A graph is a co-graph if it can be constructed using the following three operations:
- The graph with exactly one node is a co-graph (in characters ).
- For two co-graphs and the disjoint union is a co-graph.
- For two co-graphs and the disjoint sum is a co-graph.
Equivalent characterizations
The following statements are equivalent for a graph :
- is a co-graph.
- does not contain an induced path , with the undirected path denoted by four nodes.
- The complement graph of every connected induced subgraph of with at least two nodes is disconnected.
- can be constructed using the following three rules:
- Every graph with exactly one node is a co-graph.
- For two co-graphs and the disjoint union is a co-graph.
- For a co-graph , the complement graph is also a co-graph.
Co-tree
In order to be able to efficiently solve difficult problems on co-graphs, one can represent them with the help of co-trees . A co-tree is a binary tree whose leaves are marked with and whose inner nodes are marked with or .
A co-tree is defined as follows:
- The co-tree for the co-graph is the tree with a node that is marked with .
- Be and co-graphs with the co-trees and . The co-tree to the disjoint union of and consists of a root node marked with with the children and .
- Be and co-graphs with the co-trees and . The co-tree for the disjoint sum of and consists of a root node marked with with the children and .
example
The following example outlines the construction of a co-graph with an associated co-tree :
Co-graph | Representation of the co-graph | Representation of the co-tree | Co-tree |
---|---|---|---|
Other examples of co-graphs are complete graphs and completely disjoint graphs .
Properties of co-graphs
It is easy to see that co-graphs are closed with a complement . In order to generate the complement graph, only the operations and have to be swapped in the associated co-tree .
Furthermore, the set of co-graphs is completed with the formation of induced sub -graphs .
It is also known that every co-graph is a perfect graph .
Application in algorithms
Some difficult graph problems can be solved on co-graphs in linear time. These include u. A. the problems INDEPENDENT QUANTITY, CLIQUE and NODE COVERAGE .
With the help of dynamic programming on the associated co-trees, solutions to the problems mentioned can be found easily and elegantly.
literature
- 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