Cograph Editing in O(3 n n) time and O(2 n ) space.
W. Timothy J. White, Marcus Ludwig, Sebastian Böcker · arXiv (Cornell University) · 2017
We present a dynamic programming algorithm for optimally solving the \textsc{Cograph Editing} problem on an $n$-vertex graph that runs in $O(3^n n)$ time and uses $O(2^n)$ space. In this problem, we are given a graph $G = (V, E)$ and the task is to find a smallest possible set $F \subseteq V \times V$ of vertex pairs such that $(V, E \bigtriangleup F)$ is a cograph (or $P_4$-free graph), where $\bigtriangleup$ represents the symmetric difference operator. We also describe a technique for speeding up the performance of the algorithm in practice.