Kernels for deletion to classes of acyclic digraphs

作者：

Highlights：

• Pumpkin Vertex Deletion Set admits a kernel of size O(k3).

• Out-Forest Vertex Deletion Set admits a kernel of size O(k2).

• It is unlikely that Out-Forest Vertex Deletion Set admits a kernel of size O(k2−ϵ).

摘要

•Pumpkin Vertex Deletion Set admits a kernel of size O(k3).•Out-Forest Vertex Deletion Set admits a kernel of size O(k2).•It is unlikely that Out-Forest Vertex Deletion Set admits a kernel of size O(k2−ϵ).

论文关键词：Out-forest,Pumpkin,Parameterized complexity,Kernelization

论文评审过程：Received 1 October 2016, Revised 1 May 2017, Accepted 27 July 2017, Available online 1 September 2017, Version of Record 13 November 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.07.008