2014/12/23 by Pål Grønås Drange, Michał Pilipczuk, Drange, Pål Grønås +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1412.7558
openalex publication_date 2014/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a kernel with O(k7) vertices for Trivially Perfect Editing, the problem of adding or removing at most k edges in order to make a given graph trivially perfect. This answers in affirmative an open question posed by Nastos and Gao, and by Liu et al. Our general technique implies also the existence of kernels of the same size for the related problems Trivially Perfect Completion and Trivially Perfect Deletion. Whereas for the former an O(k3) kernel was given by Guo, for the latter no polynomial kernel was known. We complement our study of Trivially Perfect Editing by proving that, contrary to Trivially Perfect Completion, it cannot be solved in time 2o(k) ⋅ nO(1) unless the Exponential Time Hypothesis fails. In this manner we complete the picture of the parameterized and kernelization complexity of the classic edge modification problems for the class of trivially perfect graphs.