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=|V|$ vertices that computes a spanning tree with total weight of the internal vertices is at least β dβ d +d-2 - ε of the total weight of all the vertices of the graph for any ε>0, where β d = (d-1)Hd-1, and Hd-1 = ∑ ᵢ₌₁ᵈ⁻¹ i⁻¹ is the $(d-1)$th harmonic number. For every d ≥ 3 and n₀ ≥ 1, we show the construction of a d-regular graph of at least n₀ 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 - ε for ε>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.