Summary: We consider the Trivially Perfect Editing problem, where one is given an undirected graph \(G = (V,E)\) and a parameter \(k\in\mathbb{N}\) and seeks to edit (add or delete) at most \(k\) edges from \(G\) to obtain a trivially perfect graph. The related Trivially Perfect Completion and Trivially Perfect Deletion problems are obtained by only allowing edge additions or edge deletions, respectively. Trivially perfect graphs are both chordal and cographs, and have applications related to the tree-depth width parameter and to social network analysis. All variants of the problem are known to be NP-complete [P. Burzyn et al., Discrete Appl. Math. 154, No. 13, 1824–1844 (2006; Zbl 1110.68094); J. Nastos and Y. Gao, Soc. Networks, 35(3):439–450, 2013. doi:10.1016/j.socnet.2013.05.001] and to admit so-called polynomial kernels [P. G. Drange and M. Pilipczuk, Algorithmica 80, No. 12, 3481–3524 (2018; Zbl 1397.05070); J. Guo, Lect. Notes Comput. Sci. 4835, 915–926 (2007; Zbl 1193.68194)] More precisely, the existence of an \(O(k^3)\) vertex-kernel for Trivially Perfect Completion was announced by Guo [loc. cit.] but without a stand-alone proof. More recently, Drange and Pilipczuk [loc. cit.] provided \(O(k^7)\) vertex-kernels for these problems and left open the existence of cubic vertex-kernels. In this work, we answer positively to this question for all three variants of the problem.
For the entire collection see [Zbl 1468.68011].