A 2k-vertex kernel for maximum internal spanning tree

Wenjun Li, Jianxin Wang, Jianer Chen, Yixin Cao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

13 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783319218397
Publication statusPublished - 1 Jan 2015
Event14th International Symposium on Algorithms and Data Structures, WADS 2015 - Victoria, Canada
Duration: 5 Aug 20157 Aug 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th International Symposium on Algorithms and Data Structures, WADS 2015


  • Kernelization algorithms
  • Local-search
  • Parameterized computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A 2k-vertex kernel for maximum internal spanning tree'. Together they form a unique fingerprint.

Cite this