On Polynomial Kernelization of \mathcal {H}-free Edge Deletion

DOI10.1007/978-3-319-13524-3_3zbMATH Open1380.68210arXiv1407.7156OpenAlexW1777161231MaRDI QIDQ2946005FDOQ2946005

N. R. Aravind, Naveen Sivadasan, R. B. Sandeep

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: For a set of graphs $mathcalH$, the extsc{$mathcalH$-free Edge Deletion} problem asks to find whether there exist at most $k$ edges in the input graph whose deletion results in a graph without any induced copy of $HinmathcalH$. In cite{cai1996fixed}, it is shown that the problem is fixed-parameter tractable if $mathcalH$ is of finite cardinality. However, it is proved in cite{cai2013incompressibility} that if $mathcalH$ is a singleton set containing $H$, for a large class of $H$, there exists no polynomial kernel unless $coNPsubseteqNP/poly$. In this paper, we present a polynomial kernel for this problem for any fixed finite set $mathcalH$ of connected graphs and when the input graphs are of bounded degree. We note that there are extsc{$mathcalH$-free Edge Deletion} problems which remain NP-complete even for the bounded degree input graphs, for example extsc{Triangle-free Edge Deletion}cite{brugmann2009generating} and extsc{Custer Edge Deletion($P_3$-free Edge Deletion)}cite{komusiewicz2011alternative}. When $mathcalH$ contains $K_{1,s}$, we obtain a stronger result - a polynomial kernel for $K_t$-free input graphs (for any fixed $t>2$). We note that for $s>9$, there is an incompressibility result for extsc{$K_{1,s}$-free Edge Deletion} for general graphs cite{cai2012polynomial}. Our result provides first polynomial kernels for extsc{Claw-free Edge Deletion} and extsc{Line Edge Deletion} for $K_t$-free input graphs which are NP-complete even for $K_4$-free graphscite{yannakakis1981edge} and were raised as open problems in cite{cai2013incompressibility,open2013worker}.

Full work available at URL: https://arxiv.org/abs/1407.7156

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (2)

• Edge deletion problems: branching facilitated by modular decomposition
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems

   Recommendations

• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} 👍 👎
• A polynomial kernel for \textsc{Proper Interval Vertex Deletion} 👍 👎
• Kernel for \(K_t\)\textsc{-free Edge Deletion} 👍 👎
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems 👍 👎
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems 👍 👎
• Polynomial Kernels for Deletion to Classes of Acyclic Digraphs 👍 👎
• Polynomial kernels for deletion to classes of acyclic digraphs 👍 👎
• Interval Vertex Deletion Admits a Polynomial Kernel 👍 👎
• A polynomial kernel for distance-hereditary vertex deletion 👍 👎
• A polynomial kernel for distance-hereditary vertex deletion 👍 👎

This page was built for publication: On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946005)