I
NSTANCE
:
Graph
, a weight function
,
and positive integer
k
.
S
OLUTION
:
A subset
such that
|V'|=k
.
M
EASURE
:
Total weight of the edges in the subgraph induced by
V'
, i.e.,
Good News:
Approximable within
for some
[
242
] and [
106
].
Comment:
Also called
Heaviest Subgraph
.
Approximable within 2 if the weights satisfy the triangle inequality
[
162
].
The unweighted problem admits a PTAS if
and
[
24
].
, a weight function
,
and positive integer
k
.
such that
|V'|=k
.
for some
[
242
] and [
106
].
and
[
24
].