Turing kernelization for finding long paths and cycles in restricted graph classes

作者：

Highlights：

• Polynomial-size Turing kernels are developed for k-Path and k-Cycle.

• These problems do not have polynomial-size traditional kernels.

• We introduce the Decompose–Query–Reduce framework for preprocessing.

• For bounded-degree graphs, colored k-Path is more difficult than normal k-Path.

摘要

•Polynomial-size Turing kernels are developed for k-Path and k-Cycle.•These problems do not have polynomial-size traditional kernels.•We introduce the Decompose–Query–Reduce framework for preprocessing.•For bounded-degree graphs, colored k-Path is more difficult than normal k-Path.

论文关键词：Parameterized complexity,Turing kernelization,k-Path,Preprocessing

论文评审过程：Received 8 April 2016, Revised 19 October 2016, Accepted 23 October 2016, Available online 9 November 2016, Version of Record 19 December 2016.

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