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

Text (Author version pre-print)
2126_cocoa-v2 4.pdf - Accepted Version

Download (338kB) | Preview


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:
IITH CreatorsORCiD
Item Type: Book Section
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 18 Jan 2016 09:28
Last Modified: 20 Jan 2016 04:16
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2126 Statistics for this ePrint Item