Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
We examine the problem of determining a spanning tree of a given graph such that the number of internal nodes is maximum. The best approximation algorithm known so far for this problem is due to Prieto and Sloper and has a ratio of2. For graphs without pendant nodes, Salamon has lowered this factor to \(\frac{7}{4}\) by means of local search. However, the approximative behaviour of his algorithm on general graphs has remained open. In this paper we show that a simplified and faster version of Salamons algorithm yields a \(\frac{5}{3}\)-approximation even on general graphs. In addition to this, we investigate a node weighted variant of the problem for which Salamon achieved a ratio of 2??(G)?3. Extending Salamons approach we obtain a factor of 3+? for any ?>0. We complement our results with worst case instances showing that our analyses are tight.
approximation algorithm spanning tree