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 R 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 R 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."
['Fedor V. Fomin', 'Serge Gaspers', 'Saket Saurabh', 'Stéphan Thomassé']
A Linear Vertex Kernel for Maximum Internal Spanning Tree