Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover

摘要

This paper focuses on finding a spanning tree of a graph to maximize its internal vertices in number. We propose a new upper bound for the number of internal vertices in a spanning tree, which shows that for any undirected simple graph, any spanning tree has less internal vertices than the edges a maximum path-cycle cover has. Thus starting with a maximum path-cycle cover, we can devise an approximation algorithm with a performance ratio 3/2 for this problem on undirected simple graphs. This improves upon the best known performance ratio 5/3 achieved by the algorithm of Knauer and Spoerhase. Furthermore, we can improve the algorithm to achieve a performance ratio 4/3 for this problem on graphs without leaves.