A 2k-vertex kernel for maximum internal spanning tree

DOI10.1007/978-3-319-21840-3_41MaRDI QIDQ3449846zbMATH OpenOpenAlexFDO

Authors Wen-Jun Li, Jianxin Wang, Yixin Cao, Jianer Chen

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.8296

zbMATH Keywords

kernelization algorithmslocal searchparameterized computation

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

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}cdot{n}^{O(1)}$.

Recommendations

• A linear vertex kernel for maximum internal spanning tree
• A linear vertex kernel for Maximum Internal Spanning Tree
• Reducing to independent set structure -- the case of k-internal spanning tree
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem

Cites work

• A linear vertex kernel for maximum internal spanning tree
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A randomized linear-time algorithm to find minimum spanning trees
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Algorithms and Data Structures
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Approximating the maximum internal spanning tree problem
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Deeper local search for better approximation on maximum internal spanning trees
• Dynamic Scaling of Growing Interfaces
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Minimum leaf out-branching and related problems
• On finding spanning trees with few leaves
• On the minimum diameter spanning tree problem
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Reducing to independent set structure -- the case of k-internal spanning tree
• Representative families: a unified tradeoff-based approach
• Sharp separation and applications to exact and parameterized algorithms

Cited in

(16)

• A linear vertex kernel for maximum internal spanning tree
• Algorithms for maximum internal spanning tree problem for some graph classes
• A simple linear time algorithm to solve the MIST problem on interval graphs
• Reoptimization of parameterized problems
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• Reducing to independent set structure -- the case of k-internal spanning tree
• Spotting trees with few leaves
• Mixing Color Coding-Related Techniques
• A linear vertex kernel for Maximum Internal Spanning Tree
• Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
• Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
• Spotting trees with few leaves
• Algorithms and Data Structures
• Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• Representative families: a unified tradeoff-based approach

This page was built for publication: A \(2k\)-vertex kernel for maximum internal spanning tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449846)