A 2k-Vertex Kernel for Maximum Internal Spanning Tree

2014/12/29 by Wenjun Li, Li, Wenjun, Jianxin Wang +5
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1412.8296

arxiv created 2014/12/29 · openalex publication_date 2014/12/29 · arxiv updated 2014/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the parameterized version of the maximum internal spanning tree problem, which, given an n-vertex graph and a parameter k, asks for 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. 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 deterministic algorithm for the problem running in time 4^k ⋅ n^O(1).

Related

• A Linear Vertex Kernel for Maximum Internal Spanning Tree
• A 4/3-approximation algorithm for finding a spanning tree to maximize its internal vertices
• Exact Exponential Time Algorithms for Max Internal Spanning Tree
• An Approximation Algorithm for Maximum Internal Spanning Tree
• Approximation algorithms for the maximum weight internal spanning tree problem