MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH

• INSTANCE: Graph $G=\left(V,E\right)$, a weight function $w : E \rightarrow N$, and an integer $d\ge 2$.
• SOLUTION: A subset $E'\subseteq E$ such that the subgraph $G'=\left(V,E'\right)$ is connected and has no vertex with degree exceeding d.
• MEASURE: The total weight of the subgraph, i.e., $\sum_{e \in E'}w(E)$.

  
  

• Bad News: Not in APX for any d [Kann, --].
• Comment: Transformation from LONGEST PATH. The problems have, indeed, the same non-approximability results.
• Garey and Johnson: GT26