N R, Aravind and R B, Sandeep and Sivadasan, N
(2015)
Parameterized Lower Bound and NPCompleteness of Some HFree Edge Deletion Problems.
In:
Combinatorial Optimization and Applications 9th International Conference, COCOA 2015, Houston, TX, USA, December 1820, 2015, Proceedings.
Lecture Notes in Computer Science, 9486
.
Springer International Publishing, pp. 424438.
ISBN 9783319266251
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. We prove that Hfree Edge Deletion is NPcomplete 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 NPcomplete problems cannot be solved in parameterized subexponential time, i.e., in time 2o(k)⋅GO(1), unless Exponential Time Hypothesis fails.
[error in script]
Actions (login required)

View Item 