Complexity and parameterized algorithms for Cograph Editing

Cograph Editing is to find for a given graph G=(V,E) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we first show that this problem is NP-hard by a reduction from Exact 3-Cover. Subsequently, we present a parameterized algorithm based on a refined search tree technique with a running time of O(4.612k+|V|4.5), which improves the trivial algorithm of running time O(6k+|V|4.5).