Next: MINIMUM EDGE 2-SPANNER Up: Subgraphs and Supergraphs Previous: MAXIMUM SUBFOREST Index

### MAXIMUM EDGE SUBGRAPH

- INSTANCE: Graph , a weight function , and positive integer k.

- SOLUTION: A subset such that |V'|=k.

- MEASURE: Total weight of the edges in the subgraph induced by V', i.e.,

- Good News: Approximable within for some [317] and [145].

- Comment: Also called Heaviest Subgraph. Approximable within 2 if the weights satisfy the triangle inequality [224]. The unweighted problem admits a PTAS if and [37].