A linear vertex kernel for Maximum Internal Spanning Tree

DOI10.1007/978-3-642-10631-6_29MaRDI QIDQ3652213zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé

Publication date 17 December 2009

Published in Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

Maximum Internal Spanning Tree problempolynomial time algorithm

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: We present a polynomial time algorithm that for any graph G and integer k >= 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most 3k vertices and an integer k' such that G has a spanning tree with at least k internal vertices if and only if G' has a spanning tree with at least k' internal vertices. In other words, we show that the Maximum Internal Spanning Tree problem parameterized by the number of internal vertices k, has a 3k-vertex kernel. Our result is based on an innovative application of a classical min-max result about hypertrees in hypergraphs which states that "a hypergraph H contains a hypertree if and only if H is partition connected."

Recommendations

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

Cited in

(12)

• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Sharp separation and applications to exact and parameterized algorithms
• Reducing to independent set structure -- the case of k-internal spanning tree
• A 2k-vertex kernel for maximum internal spanning tree
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• On the directed full degree spanning tree problem
• Lower bounds on kernelization
• Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
• Kernelization for finding lineal topologies (depth-first spanning trees) with many or few leaves
• On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

This page was built for publication: A linear 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 Q3652213)