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. 61 2 k + | V | 4. 5 ), which improves the trivial algorithm of running time O ( 6 k + | V | 4. 5 ).

Authors

• Yunlong Liu
• Jianxin Wang
• Jiong Guo
• Jianer Chen

Keywords

• Cograph Editing
• NP-hardness
• Parameterized algorithms
• P 4 -sparse graph