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. ${\displaystyle G=(V,E)}$

definition

Illustration of a co-graph. As you can see, there is no induced one . ${\displaystyle P_{4}}$

This graph is not a co-graph as it contains an induced one . ${\displaystyle P_{4}}$

A graph is a co-graph if it can be constructed using the following three operations: ${\displaystyle G=(V,E)}$

1. The graph with exactly one node is a co-graph (in characters ). ${\displaystyle K_{1}}$ ${\displaystyle K_{1}=\bullet }$
2. For two co-graphs and the disjoint union is a co-graph. ${\displaystyle G_{1}=(V_{1},E_{1})}$ ${\displaystyle G_{2}=(V_{2},E_{2})}$ ${\displaystyle G_{1}\cup G_{2}:=(V_{1}\cup V_{2},E_{1}\cup E_{2})}$
3. For two co-graphs and the disjoint sum is a co-graph. ${\displaystyle G_{1}=(V_{1},E_{1})}$ ${\displaystyle G_{2}=(V_{2},E_{2})}$ ${\displaystyle G_{1}\times G_{2}:=(V_{1}\cup V_{2},E_{1}\cup E_{2}\cup \lbrace \lbrace u,v\rbrace |u\in V_{1},v\in V_{2}\rbrace )}$

Equivalent characterizations

The following statements are equivalent for a graph : ${\displaystyle G}$

• ${\displaystyle G}$ is a co-graph.
• ${\displaystyle G}$does not contain an induced ${\displaystyle P_{4}}$path , with the undirected path denoted by four nodes. ${\displaystyle P_{4}}$
• The complement graph of every connected induced subgraph of with at least two nodes is disconnected. ${\displaystyle G}$
• ${\displaystyle G}$ can be constructed using the following three rules:

1. Every graph with exactly one node is a co-graph. ${\displaystyle K_{1}}$
2. For two co-graphs and the disjoint union is a co-graph. ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle G_{1}\cup G_{2}}$
3. For a co-graph , the complement graph is also a co-graph. ${\displaystyle G}$ ${\displaystyle {\bar {G}}}$

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 . ${\displaystyle \bullet }$ ${\displaystyle \cup }$ ${\displaystyle \times }$

A co-tree is defined as follows: ${\displaystyle T}$

1. The co-tree for the co-graph is the tree with a node that is marked with . ${\displaystyle T}$ ${\displaystyle G=\bullet }$ ${\displaystyle \bullet }$
2. 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 . ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle \cup }$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$
3. 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 . ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle \times }$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

example

The following example outlines the construction of a co-graph with an associated co-tree : ${\displaystyle G_{5}}$ ${\displaystyle T_{5}}$

Co-graph	Representation of the co-graph	Representation of the co-tree	Co-tree
${\displaystyle G_{1}=\bullet }$			${\displaystyle T_{1}}$
${\displaystyle G_{2}=G_{1}\cup G_{1}}$			${\displaystyle T_{2}}$
${\displaystyle G_{3}=G_{1}\times G_{2}}$			${\displaystyle T_{3}}$
${\displaystyle G_{4}=G_{3}\cup G_{3}}$			${\displaystyle T_{4}}$
${\displaystyle G_{5}=G_{1}\times G_{4}}$			${\displaystyle T_{5}}$

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 . ${\displaystyle \cup }$ ${\displaystyle \times }$

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