- INSTANCE:
Graph
,
a weight function
,
and positive integer
*k*. - SOLUTION: A subset such that .
- MEASURE:
Total weight of the edges in the subgraph induced by
*V'*, i.e.,

*Good News:*Approximable within for some [157].*Comment:*Also called*Dense*, or*k*-subgraph*Heavy subgraph*. Approximable within 2 if the weights satisfy the triangle inequality [241]. The unweighted problem admits a PTAS if and [39].