The full-degree spanning tree problem

The full-degree spanning tree problem is defined as follows: Given a connec ted graph G = (V, E), find a spanning tree T to maximize the number of vert ices whose degree in T is the same as in G (these are called vertices of "f ull" degree). This problem is NP-hard. We present almost-optimal approximat ion algorithms for it assuming that coR not equal NP, For the case of gener al graphs, our approximation factor is Theta(rootn). Using Hastad'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-epsilon)) then coR = NP. Additionally, we present two algorithms for optimally solving small instances of the general problem and experimental r esults comparing our algorithm to the optimal solution and the previous heu ristic used for this problem, (C) 2000 John Wiley & Sons, Inc.