Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems

N R, Aravind and R B, Sandeep and Sivadasan, N (2016) Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems. In: LATIN 2016: Theoretical Informatics (12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings). Lecture Notes in Computer Science, 9644 . Springer Berlin Heidelberg, pp. 82-95. ISBN 978-3-662-49529-2

[img]
Preview
Text
2275_1509.08807.pdf - Accepted Version

Download (437kB) | 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. H-free Edge Completion and H-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that H-free Edge Deletion is NP-complete if and only if H is a graph with at least two edges, H-free Edge Completion is NP-complete if and only if H is a graph with at least two non-edges and H-free Edge Editing is NP-complete if and only if H is a graph with at least three vertices. Our result on H-free Edge Editing resolves a conjecture by Alon and Stav (2009). Additionally, we prove 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. Furthermore, we obtain implications on the incompressibility of these problems.

[error in script]
IITH Creators:
IITH CreatorsORCiD
N R, AravindUNSPECIFIED
Sivadasan, NUNSPECIFIED
Item Type: Book Section
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 15 Apr 2016 04:29
Last Modified: 15 Apr 2016 04:29
URI: http://raiith.iith.ac.in/id/eprint/2275
Publisher URL: http://dx.doi.org/10.1007/978-3-662-49529-2_7
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2275 Statistics for this ePrint Item