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

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

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

Publication date 15 September 2015

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

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)

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}.

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

Cited in

(11)

• Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
• Two edge modification problems without polynomial kernels
• On generating triangle-free graphs
• Polynomial kernelization for removing induced claws and diamonds
• Two edge modification problems without polynomial kernels
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• A polynomial kernel for diamond-free editing
• Kernel for \(K_t\)\textsc-free Edge Deletion
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• Edge deletion problems: branching facilitated by modular decomposition

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)