A linear vertex kernel for maximum internal spanning tree

We present a polynomial time algorithm that for any graph G   and integer k⩾0k⩾0, either finds a spanning tree with at least k   internal vertices, or outputs a new graph GRGR on at most 3k   vertices and an integer k′k′ such that G has a spanning tree with at least k   internal vertices if and only if GRGR has a spanning tree with at least k′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.”

► First linear kernel for Maximum Internal Spanning Tree.
► Uses a classical min–max result about hypertrees by Frank et al. (2003) [6].
► Shows another application of the c-expansion lemma of Thomassé (2010) [16].