2014/07/26 by N. R. Aravind, R. B. Sandeep, Aravind, N. R. +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1407.7156
12 pages. IPEC 2014 accepted paper
arxiv created 2014/11/18 · arxiv updated 2014/11/19
For a set of graphs H, the \textscH-free Edge Deletion problem asks to find whether there exist at most k edges in the input graph whose deletion results in a graph without any induced copy of H\inH. In \citecai1996fixed, it is shown that the problem is fixed-parameter tractable if H is of finite cardinality. However, it is proved in \citecai2013incompressibility that if H is a singleton set containing H, for a large class of H, there exists no polynomial kernel unless coNP⊆ NP/poly. In this paper, we present a polynomial kernel for this problem for any fixed finite set H of connected graphs and when the input graphs are of bounded degree. We note that there are \textscH-free Edge Deletion problems which remain NP-complete even for the bounded degree input graphs, for example Triangle-free Edge Deletion\citebrugmann2009generating and Custer Edge Deletion(P3-free Edge Deletion)\citekomusiewicz2011alternative. When H contains K1,s, we obtain a stronger result - a polynomial kernel for Kt-free input graphs (for any fixed t> 2). We note that for s>9, there is an incompressibility result for \textscK1,s-free Edge Deletion for general graphs \citecai2012polynomial. Our result provides first polynomial kernels for Claw-free Edge Deletion and Line Edge Deletion for Kt-free input graphs which are NP-complete even for K4-free graphs\citeyannakakis1981edge and were raised as open problems in \citecai2013incompressibility,open2013worker.