Cograph - Computational Properties

Computational Properties

Cographs may be recognized in linear time, and a cotree representation constructed, using modular decomposition (Corneil, Perl & Stewart 1985), partition refinement (Habib & Paul 2005), or split decomposition (Gioan & Paul 2008). Once a cotree representation has been constructed, many familiar graph problems may be solved via simple bottom-up calculations on the cotrees.

For instance, to find the maximum clique in a cograph, compute in bottom-up order the maximum clique in each subgraph represented by a subtree of the cotree. For a node labeled 0, the maximum clique is the maximum among the cliques computed for that node's children. For a node labeled 1, the maximum clique is the union of the cliques computed for that node's children, and has size equal to the sum of the children's clique sizes. Thus, by alternately maximizing and summing values stored at each node of the cotree, we may compute the maximum clique size, and by alternately maximizing and taking unions, we may construct the maximum clique itself. Similar bottom-up tree computations allow the maximum independent set, vertex coloring number, maximum clique cover, and Hamiltonicity (that is the existence of a Hamiltonian cycle) to be computed in linear time from a cotree representation of a cograph. One can also use cotrees to determine in linear time whether two cographs are isomorphic.

If H is an induced subgraph of a cograph G, then H is itself a cograph; the cotree for H may be formed by removing some of the leaves from the cotree for G and then suppressing nodes that have only one child. It follows from Kruskal's tree theorem that the relation of being an induced subgraph is a well-quasi-ordering on the cographs (Damaschke 1990). Thus, if a subfamily of the cographs (such as the planar cographs) is closed under induced subgraph operations then it has a finite number of forbidden induced subgraphs. Computationally, this means that testing membership in such a subfamily may be performed in linear time, by using a bottom-up computation on the cotree of a given graph to test whether it contains any of these forbidden subgraphs.