TY - GEN
T1 - A 2k-vertex kernel for maximum internal spanning tree
AU - Li, Wenjun
AU - Wang, Jianxin
AU - Chen, Jianer
AU - Cao, Yixin
PY - 2015/1/1
Y1 - 2015/1/1
N2 - We consider the parameterized version of the maximum internal spanning tree problem: given an n-vertex graph and a parameter k, does the graph have a spanning tree with at least k internal vertices? Fomin et al. [J. Comput. System Sci., 79:1-6] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel for this problem. Here we propose a novel way to use the same reduction rule, resulting in an improved 2k-vertex kernel. Our algorithm applies first a greedy procedure consisting of a sequence of local exchange operations, which ends with a local-optimal spanning tree, and then uses this special tree to find a reducible structure. As a corollary of our kernel, we obtain a 4k·nO(1)-time deterministic algorithm, improving all previous algorithms for the problem.
AB - We consider the parameterized version of the maximum internal spanning tree problem: given an n-vertex graph and a parameter k, does the graph have a spanning tree with at least k internal vertices? Fomin et al. [J. Comput. System Sci., 79:1-6] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel for this problem. Here we propose a novel way to use the same reduction rule, resulting in an improved 2k-vertex kernel. Our algorithm applies first a greedy procedure consisting of a sequence of local exchange operations, which ends with a local-optimal spanning tree, and then uses this special tree to find a reducible structure. As a corollary of our kernel, we obtain a 4k·nO(1)-time deterministic algorithm, improving all previous algorithms for the problem.
KW - Kernelization algorithms
KW - Local-search
KW - Parameterized computation
UR - http://www.scopus.com/inward/record.url?scp=84951811884&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-21840-3_41
DO - 10.1007/978-3-319-21840-3_41
M3 - Conference article published in proceeding or book
SN - 9783319218397
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 495
EP - 505
BT - Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
PB - Springer Verlag
T2 - 14th International Symposium on Algorithms and Data Structures, WADS 2015
Y2 - 5 August 2015 through 7 August 2015
ER -