Parameterized lower bound and NP-completeness of some H-free Edge Deletion problems

2015/07/22 by N. R. Aravind, R. B. Sandeep, Aravind, N. R. +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1507.06341

15 pages, COCOA 15 accepted paper

arxiv created 2015/09/12 · arxiv updated 2015/09/15

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 2^o(k)⋅ |G|^O(1), unless Exponential Time Hypothesis fails.

Cited by

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

Related

• Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
• Hardness of approximation for H-free edge modification problems
• On Polynomial Kernelization of H-free Edge Deletion
• Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion
• Incompressibility of H-free edge modification problems: Towards a dichotomy