Approximation algorithms for maximum weighted internal spanning trees in regular graphs and subdivisions of graphs

Let G be a vertex-weighted connected graph of n vertices and let T be a spanning tree of G. We call T a maximum weighted internal spanning tree of G if the sum of the weights of the internal vertices of T is the maximum over all spanning trees of G. The maximum weighted internal spanning tree (MaxwIST) problem asks to find such a spanning tree T of G. The problem is NP-hard. We give an O(dn) time approximation algorithm for d-regular graphs of n=vertical bar V vertical bar vertices that computes a spanning tree with total weight of the internal vertices is at least beta(d)/beta(d) + (d - 2) - epsilon of the total weight of all the vertices of the graph for any epsilon > 0, where beta(d) = (d-1)Hd-1, and Sigma(d-1)(i=1) i(-1) is the (d-1)th harmonic number. For every d >= 3 and n(0) >= 1, we show the construction of a d-regular graph of at least n(0) vertices, such that for any of its spanning trees, w(I)/w(V) <= d/d+1 holds. We give an O(dn) time approximation algorithm for subdivisions of d-regular graphs, where the ratio of the internal weight of the spanning tree with the total vertex weight of the graph is at least d-1/2d-3-epsilon for epsilon > 0. We extend our study to x-subdivisions of Hamiltonian and hypoHamiltonian graphs, where each edge of the original Hamiltonian or hypoHamiltonian graph has been subdivided at least x times. For those two graph classes, we show that there exists a spanning tree with internal vertex weight at least 1-2/x-1 of the total vertex weight of the graph. Furthermore, we give O(n) time algorithm for x-subdivisions of biconnected outerplanar graphs and 4-connected planar graphs to achieve the above bound.