Linear kernels for separating a graph into components of bounded size

作者：

Highlights：

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

• We give a non-trivial extension of the expansion lemma, called the weighted expansion lemma.

• We obtain an O(pk) kernel for the p-size separator problem.

摘要

•We obtain a generalization of Nemhauser and Trotter's local optimization theorem.•We give a non-trivial extension of the expansion lemma, called the weighted expansion lemma.•We obtain an O(pk) kernel for the p-size separator problem.

论文关键词：Balanced separators,FPT,Graph algorithms,Linear kernels,NT-Theorem

论文评审过程：Received 8 December 2016, Revised 12 April 2017, Accepted 17 April 2017, Available online 5 May 2017, Version of Record 11 June 2017.

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