A quasi-quadratic vertex Kernel for Cograph edge editing

Christophe Crespelle, Rémi Pellerin, Stéphan Thomassé

We provide a $O(k^2\log k)$ vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reductio…