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 G (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(n1/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.
