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

July 22, 2015 Β· Declared Dead Β· πŸ› International Conference on Combinatorial Optimization and Applications

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors N. R. Aravind, R. B. Sandeep, Naveen Sivadasan arXiv ID 1507.06341 Category cs.DS: Data Structures & Algorithms Citations 2 Venue International Conference on Combinatorial Optimization and Applications Last Checked 4 months ago
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted