2009/07/20 by Fedor V. Fomin, Serge Gaspers, Fomin, Fedor V. +5 · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Discrete mathematics #F.2.2 #FOS: Computer and information sciences #G.2.2 #Graph #Graph power #Hypergraph #Limits and Structures in Graph Theory #Line graph #Mathematics #Minimum degree spanning tree #Partition (number theory) #Shortest-path tree #Spanning tree #Vertex (graph theory) #Wheel graph #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0907.3208
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2009/07/20 · arxiv created 2012/03/03 · arxiv updated 2012/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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."