Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem

Given a vertex-weighted connected graph G = (V, E), the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13/17. The currently best approximation algorithm for MwIST only has a performance ratio of 1/3−ϵ, for any ϵ > 0. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.