A Fully Dynamic Algorithm for Modular Decomposition and Recognition of Cographs

The problem of dynamically recognizing a graph property calls for efficiently deciding if an input graph satisfies the property under repeated modifications to its set of vertices and edges. The input to the problem consists of a series of modifications to be performed on the graph. The objective is to maintain a representation of the graph as long as the property holds, and to detect when it ceases to hold.

In the talk I will present an essentially optimal algorithm for recognizing cographs, working in constant time per edge modification and $O(d)$ time per $d$-degree vertex modification.  Our approach is based on maintaining the modular decomposition tree of the dynamic graph, and using this tree for the recognition.

Joint work with Ron Shamir, Tel-Aviv University.