On a generalization of Nemhauser and Trotter's local optimization theorem

作者：

Highlights：

• We prove a generalization of Nemhauser and Trotter's local optimization theorem.

• We obtain the first linear kernel for d-Bounded-Degree Vertex Deletion parameterized by the deletion size k for each fixed d≥3.

• We obtain the first linear kernel for d-Star Packing parameterized by the packing size k for each fixed d≥3.

摘要

•We prove a generalization of Nemhauser and Trotter's local optimization theorem.•We obtain the first linear kernel for d-Bounded-Degree Vertex Deletion parameterized by the deletion size k for each fixed d≥3.•We obtain the first linear kernel for d-Star Packing parameterized by the packing size k for each fixed d≥3.

论文关键词：Kernelization,Fixed-parameter tractable,Graph algorithms,Graph theory,Graph decomposition,Bounded-degree vertex deletion

论文评审过程：Received 24 September 2015, Revised 11 June 2016, Accepted 24 August 2016, Available online 9 September 2016, Version of Record 14 November 2016.

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