| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435719 | Theoretical Computer Science | 2015 | 8 Pages |
Abstract
We study the parameterized complexity of the following Split Contraction problem: Given a graph G, and an integer k as parameter, determine whether G can be modified into a split graph by contracting at most k edges. We show that Split Contraction can be solved in FPT time 2O(k2)n52O(k2)n5, but admits no polynomial kernel unless NP⊆coNP/polyNP⊆coNP/poly.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chengwei Guo, Leizhen Cai,