Title of Paper:An improved linear kernel for the cycle contraction problem

Hits:

Affiliation of Author(s):计算机科学与技术学院/人工智能学院/软件学院

Journal:Inf. Process. Lett.

Abstract:The problem of modifying a given graph to satisfy certain properties has been one of the central topics in parameterized tractability study. In this paper, we investigate the cycle contraction problem, which makes a graph into a cycle by edge contractions. The problem was raised by Belmonte et al. [IPEC 2013] and they obtained a linear kernel with at most 6k+6 vertices for it. We provide an improved kernel with at most 5k+4 vertices for the problem in this paper. Our result showcases how to design kernelization algorithm for one problem by exploiting kernels of another problem. © 2019 Elsevier B.V.

ISSN No.:0020-0190

Translation or Not:no

Date of Publication:2019-09-01

Co-author:Sun, Yuefang

Correspondence Author:shengbin