A single-exponential FPT algorithm for the K4-minor cover problem

作者：

Highlights：

• We provide an efficient FPT algorithm for the K4-minor cover problem.

• It combines iterative compression with protrusion reduction and branching.

• It extends previous algorithms for Vertex Cover and Feedback Vertex Set.

摘要

•We provide an efficient FPT algorithm for the K4-minor cover problem.•It combines iterative compression with protrusion reduction and branching.•It extends previous algorithms for Vertex Cover and Feedback Vertex Set.

论文关键词：Treewidth-2 Deletion,Fixed-parameter tractable algorithms,K4-minor cover

论文评审过程：Received 20 September 2012, Revised 8 March 2014, Accepted 18 April 2014, Available online 14 May 2014.

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