Approximating the Maximum Internal Spanning Tree problem

Abstract

Given an undirected connected graph $G$ we consider the problem of finding a spanning tree of $G$ which has a maximum number of internal (non-leaf) vertices among all spanning trees of $G$. This problem, called Maximum Internal Spanning Tree problem, is clearly NP-hard since it is a generalization of the Hamiltonian Path problem. From the optimization point of view the Maximum Internal Spanning Tree problem is equivalent to the Minimum Leaf Spanning Tree problem. However, the two problems have different approximability properties. Lu and Ravi proved that the latter has no constant factor approximation–unless P = NP–, while Salamon and Wiener gave a linear-time 2-approximation algorithm for the Maximum Internal Spanning Tree problem.

In this paper, we improve this approximation ratio by giving an $\mathcal{O}\left({\left|V\left(G\right)\right|}^4\right)$-time$7/4$-approximation algorithm for graphs without pendant vertices. Our approach is based on the successive execution of local improvement steps. We use a linear programming formulation and a primal–dual technique to prove the approximation ratio. We also investigate the vertex-weighted case, that is to find a spanning tree of a vertex-weighted graph $G$ in which the weight sum of internal vertices is maximal among all spanning trees of $G$. For this problem we present a $(2\Delta \left(G\right)-3)$-approximation algorithm, where $\Delta \left(G\right)$ is the maximum vertex-degree of $G$. A slight modification of this algorithm ensures a 2-approximation whenever the input graph is claw-free. Both algorithms run in $\mathcal{O}\left({\left|V\left(G\right)\right|}^4\right)$ time for graphs with no pendant vertices.