Fully dynamic recognition algorithm and certificate for directed cographs

This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G  , the algorithm supports arc and vertex modification (insertion or deletion) in O(d)O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated; otherwise, a certificate is returned within the same complexity.