Name
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 vertices 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 properties', is hence NP-complete and unlikely to admit a polynomial time approximation algorithm with approximation factor smaller than 2. In the framework of parameterized complexity, 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14355-7_10 | AAIM |
Keywords | Field | DocType |
vertex cover,cycle packing problem,polynomial time approximation algorithm,approximation factor,fpt algorithm,super-linear kernel,node-deletion problem,cycle packing,fundamental problem,kernelization algorithm,bounded-degree vertex deletion,graph theory,computational biology,parameterized complexity | Kernelization,Discrete mathematics,Parameterized complexity,Combinatorics,Mathematical optimization,Edge cover,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Vertex cover,Feedback vertex set,Mathematics | Conference |
Volume | ISSN | ISBN |
6124 | 0302-9743 | 3-642-14354-7 |
Citations | PageRank | References |
7 | 0.48 | 9 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhi-Zhong Chen | 1 | 481 | 45.46 |
| Michael R. Fellows | 2 | 4138 | 319.37 |
| Bin Fu | 3 | 224 | 23.51 |
| Haitao Jiang | 4 | 25 | 2.37 |
| Yang Liu | 5 | 7 | 0.48 |
| Lusheng Wang | 6 | 2433 | 224.97 |
| Binhai Zhu | 7 | 903 | 109.96 |