Win-win kernelization for degree sequence completion problems

作者：

Highlights：

• We describe interactions between number and graph problems.

• f-Factor computations allow to link number and graph problems.

• We present a win-win kernelization framework for edge insertion problems.

• Maximum vertex degree governs the complexity of degree sequence completion problems.

摘要

•We describe interactions between number and graph problems.•f-Factor computations allow to link number and graph problems.•We present a win-win kernelization framework for edge insertion problems.•Maximum vertex degree governs the complexity of degree sequence completion problems.

论文关键词：Computational complexity,NP-hardness,Polynomial problem kernels,f-Factors,Lower bounds for problem kernels,Data reduction

论文评审过程：Received 6 May 2014, Revised 7 July 2015, Accepted 31 March 2016, Available online 13 April 2016, Version of Record 10 June 2016.

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