Cograph编辑的复杂度和参数化算法

Cograph编辑是针对给定的图G =（V，E）找到一组最多k个边缘添加和删除的集合，这些添加和删除将G转换为一个cograph。 该问题的计算复杂度在过去是公开的。 在本文中，我们首先通过从Exact3-Cover的归纳中证明这个问题是NP-hard <br>。 随后，我们基于运行时间为O（4.612 ^ k + | V | ^ 4.5）的精细搜索树技术，提出了一种参数化算法<br>，该算法改进了运行时间为O（6）的平凡算法。 ^ k + | V | ^ 4.5）。