N R, Aravind and R B, Sandeep and Sivadasan, N
(2016)
Parameterized Lower Bounds and Dichotomy Results for the NPcompleteness of Hfree Edge Modification Problems.
In:
LATIN 2016: Theoretical Informatics (12th Latin American Symposium, Ensenada, Mexico, April 1115, 2016, Proceedings).
Lecture Notes in Computer Science, 9644
.
Springer Berlin Heidelberg, pp. 8295.
ISBN 9783662495292
Abstract
For a graph H, the Hfree 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. Hfree Edge Completion and Hfree 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 Hfree Edge Deletion is NPcomplete if and only if H is a graph with at least two edges, Hfree Edge Completion is NPcomplete if and only if H is a graph with at least two nonedges and Hfree Edge Editing is NPcomplete if and only if H is a graph with at least three vertices. Our result on Hfree Edge Editing resolves a conjecture by Alon and Stav (2009). Additionally, we prove that, these NPcomplete problems cannot be solved in parameterized subexponential time, i.e., in time 2o(k)⋅GO(1), unless Exponential Time Hypothesis fails. Furthermore, we obtain implications on the incompressibility of these problems.
[error in script]
Actions (login required)

View Item 