The full-degree spanning tree problem

Randeep Bhatia, Samir Khuller, Robert Pless*, Yoram J. Sussmann

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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(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.

Original languageEnglish (US)
Pages (from-to)203-209
Number of pages7
Issue number4
StatePublished - Dec 2000


  • Algorithm
  • Approximation
  • Full degree
  • Graph
  • NP-hardness
  • Spanning tree

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'The full-degree spanning tree problem'. Together they form a unique fingerprint.

Cite this