Approximation of Dense-$k$-Subgraph

Han, Ye and Zhang

We consider the DENSE-$k$-SUBGRAPH problem, i.e., determine a block of $k$ nodes of a weighted graph (of $n$ nodes) such that the total edge weight within the subgraph induced by the block is maximized. we present two approximation algorithms for this problem which are based on linear programming (LP) and semidefinite programming (SDP) relaxations, respectively. Our (LP) relaxation based algorithm matches the previously best known performance guarantee $\frac{k}{n}$, which was obtained by Feige and Seltser~\cite{Feige2} using an SDP relaxation. Our second approximation algorithm is based on a strengthened SDP relaxation comparing with that of Feige and Seltser~\cite{Feige2} and Srivastav and Wolf~\cite{Srivastav}, and it achieves the presently best performance guarantee for a wide range of $k$.

Department of Management Sciences\\ Henry B. Tippie College of Business The University of Iowa Iowa City, IA 52242, USA, February, 2000