A Linear Vertex Kernel for Maximum Internal Spanning Tree

Fedor V. Fomin 1 Serge Gaspers 2 Saket Saurabh 1 Stéphan Thomassé 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We present a polynomial time algorithm that for any graph G and integer k 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."
Type de document :
Communication dans un congrès
ISAAC'09: 20th International Symposium on Algorithms and Computation, pp.9, 2009
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432674
Contributeur : Serge Gaspers <>
Soumis le : lundi 16 novembre 2009 - 21:10:34
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00432674, version 1

Collections

Citation

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé. A Linear Vertex Kernel for Maximum Internal Spanning Tree. ISAAC'09: 20th International Symposium on Algorithms and Computation, pp.9, 2009. 〈lirmm-00432674〉

Partager

Métriques

Consultations de la notice

63