Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems

N R, Aravind and R B, Sandeep and Sivadasan, N (2015) Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems. In: Combinatorial Optimization and Applications 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings. Lecture Notes in Computer Science, 9486 . Springer International Publishing, pp. 424-438. ISBN 978-3-319-26625-1

Preview

Text (Author version pre-print)
2126_cocoa-v2 4.pdf - Accepted Version
Download (338kB) | Preview

Abstract

For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose deletion from the input graph G results in a graph without any induced copy of H. We prove that H-free Edge Deletion is NP-complete if H is a graph with at least two edges and H has a component with maximum number of vertices which is a tree or a regular graph. Furthermore, we obtain that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time 2o(k)⋅|G|O(1), unless Exponential Time Hypothesis fails.

[error in script]

IITH Creators: