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

### MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH

- INSTANCE: Graph , a weight function , and an integer .

- SOLUTION: A subset such that the subgraph is connected and has no vertex with degree exceeding d.

- MEASURE: The total weight of the subgraph, i.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