A 43-approximation algorithm for the Maximum Internal Spanning Tree Problem

Abstract In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G, the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4 3 , which improves upon the best known performance ratio 3 2 . Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4 3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard.