We give a kernel with O(k~7) 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 (Social Networks, 35(3):439-450, 2013) and by Liu, Wang, and Guo (Tsinghua Science and Technology, 19(4):346-357, 2014). Using our technique one can also obtain kernels of the same size for the related problems, TRIVIALLY PERFECT COMPLETION and TRIVIALLY PERFECT DELETION. We complement our study of TRIVIALLY PERFECT EDITING by proving that, contrary to TRIVIALLY PERFECT COMPLETION, it cannot be solved in time 2~(o(k)) · n~(O(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.
展开▼
