MINIMUM GEOMETRIC 3-DEGREE SPANNING TREE

• INSTANCE: Set $P\subseteq Z\times Z$ of points in the plane.

• SOLUTION: A spanning tree T for P in which no vertex has degree larger than 3.

• MEASURE: The total weight of the spanning tree, i.e., $\sum_{(u,v) \in T}d(u,v)$, where d(u,v) is the Euclidean distance between u and v.

  
  

• Good News: Admits a PTAS [33].

• Comment: The 4-degree spanning tree problem also admits a PTAS, but the NP-hardness of the problem is open [33]. The 5-degree problem is polynomial-time solvable. In d-dimensional Euclidean space for $d\ge 3$ the 3-degree spanning tree problem is approximable within 5/3. [316].

  The generalization to a graph with metric weight function and for each vertex $v\in V$Ýa degree bound d(v) is called MINIMUM BOUNDED DEGREE SPANNING TREE and is approximable within $2-\min_{v\in V}\{(d(v)-2)/(d_T(v)-2): d_T(v)>2\}$, where $d_T(v)$ is the initial degree of v [158].