2022/12/30 by Crespelle, Christophe, Pellerin, Rémi, Thomassé, Stéphan
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2212.14814
We provide a O(k2 log k) vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reduction rules. We generalize one of their rules, based on packing of induced paths of length four, by introducing t-modules, which are modules up to t edge modifications. The key fact is that large t-modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra log k factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable.