MAXIMUM EDGE SUBGRAPH

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

INSTANCE: Graph $G=\left(V,E\right)$ , a weight function $w : E \rightarrow N$ , and positive integer k.
SOLUTION: A subset $V' \subseteq V$ such that $\vert V'\vert=k$ .
MEASURE: Total weight of the edges in the subgraph induced by V', i.e.,

$\begin{displaymath} \sum_{(u,v)\in E\cap(V'\times V')} w(u,v). \end{displaymath}$
Good News: Approximable within $O(\vert V\vert^{1/3-\varepsilon })$ for some $\varepsilon >0$ [157].
Comment: Also called Dense k-subgraph, or Heavy subgraph. Approximable within 2 if the weights satisfy the triangle inequality [241]. The unweighted problem admits a PTAS if $\vert E\vert =\Theta(\vert V\vert^2)$ and $k=\Theta(\vert V\vert)$ [39].

Viggo Kann
2000-03-20