The full-degree spanning tree problem

The full-degree spanning tree problem is defined as follows: Given a connected graph G = (V, E), find a spanning tree T to maximize the number of vertices whose degree in T is the same as in G (these are called vertices of "full" degree). This problem is NP-hard. We present almost-optimal approximation algorithms for it assuming that coR ≠ NP. For the case of general graphs, our approximation factor is Θ(√n). Using Håstad's result on the hardness of an approximating clique, we can show that if there is a polynomial time approximation algorithm for our problem with a factor of O(n^1/2-∈) then coR = NP. Additionally, we present two algorithms for optimally solving small instances of the general problem and experimental results comparing our algorithm to the optimal solution and the previous heuristic used for this problem.