MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH

Next: MAXIMUM PLANAR SUBGRAPH Up: Subgraphs and Supergraphs Previous: MINIMUM VERTEX DELETION TO Index

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

Viggo Kann
2000-03-20