Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

A Linear Kernel for Co-Path Cycle Packing

Chen, Zhi-Zhong, Fellows, Michael R., Fu, Bin, Jiang, Haitao, Liu, Yang, Wang, Lusheng and Zhu, Binhai (2010). A Linear Kernel for Co-Path Cycle Packing. In: AAIM 2010. 6th International Conference on Algorithmic Aspects in Information and Management, Weihai, 19-21 Jul 2010.

Document type: Conference Paper

IRMA ID 83093774xPUB7
Author Chen, Zhi-Zhong
Fellows, Michael R.
Fu, Bin
Jiang, Haitao
Liu, Yang
Wang, Lusheng
Zhu, Binhai
Title A Linear Kernel for Co-Path Cycle Packing
Conference Name AAIM 2010. 6th International Conference on Algorithmic Aspects in Information and Management
Conference Location Weihai
Conference Dates 19-21 Jul 2010
Conference Publication Title Lecture Notes in Computer Science
Place of Publication Berlin
Publisher Springer
Publication Year 2010
Volume Number 6
Issue Number 2010
ISSN 0302-9743   (check CDU catalogue open catalogue search in new window)
Start Page 90
End Page 102
Total Pages 12
HERDC Category E1 - Conference Publication (DIISR)
Abstract Bounded-Degree Vertex Deletion is a fundamental problem in graph theory that has new applications in computational biology. In this paper, we address a special case of Bounded-Degree Vertex Deletion, the Co-Path/Cycle Packing problem, which asks to delete as few ver- tices as possible such that the graph of the remaining (residual) vertices is composed of disjoint paths and simple cycles. The problem falls into the well-known class of ’node-deletion problems with hereditary prop-erties’, is hence NP-complete and unlikely to admit a polynomial time approximation algorithm with approximation factor smaller than 2. In the framework of parameterized compl exity, we present a kernelization algorithm that produces a kernel with at most 37k vertices, improving on the super-linear kernel of Fellows et al.’s general theorem for Bounded-Degree Vertex Deletion. Using this kernel, and the method of bounded search trees, we devise an FPT algorithm that runs in time O∗(3.24k). On the negative side, we show that the problem is APX-hard and unlikely to have a kernel smaller than 2k by a reduction from Vertex Cover.
 
Versions
Version Filter Type
Access Statistics: 81 Abstract Views, 4 File Downloads  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:13:55 CST