A Polynomial Kernel for Trivially Perfect Editing

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 (Soc Netw 35(3):439–450, 2013 ), and by Liu et al. (Tsingh...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2018, Vol.80 (12), p.3481-3524
Main Authors: Drange, Pål Grønås, Pilipczuk, Michał
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Deletion
Editing
Graph theory
Mathematics of Computing
Polynomials
Theory of Computation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (Soc Netw 35(3):439–450, 2013 ), and by Liu et al. (Tsinghua Sci Technol 19(4):346–357, 2014 ). Our general technique implies also the existence of kernels of the same size for related Trivially Perfect Completion and Trivially Perfect Deletion problems. Whereas for the former an O ( k 3 ) kernel was given by Guo (in: ISAAC 2007, LNCS, vol 4835, Springer, pp 915–926, 2007 ), 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 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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-017-0401-6