pith. sign in

arxiv: 1507.06341 · v2 · pith:7T4OD3QZnew · submitted 2015-07-22 · 💻 cs.DS

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

classification 💻 cs.DS
keywords graphdeletionedgefreetimeedgesnp-completeparameterized
0
0 comments X
read the original 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)}\cdot |G|^{O(1)}$, unless Exponential Time Hypothesis fails.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.