[BR08] A Deterministic Approximation Algorithm for the Densest k-Subgraph Problem

Revue Internationale avec comité de lecture : Journal International Journal of Operational Research, vol. 3(3), pp. 301-314, 2008, (doi:10.1504/IJOR.2008.017534)

Mots clés: Densest k-Subgraph Problem ; Approximation algorithms ; Detreministic ; Linear programming

Résumé: In the Densest k-Subgraph problem (DSP), we are given an undirected weighted graph G=(V,E) with n vertices v1,...,vn. We seek to find a subset of k vertices (k belonging to {1,...,n}) which maximizes the number of edges which have their two endpoints in the subset. This problem is NP-hard even for bipartite graphs, and no polynomial-time algorithm with a fixed performance guarantee is known for the general case. Several authors have proposed randomized approximation algorithms for particular cases (especially when k=n/c, c>1). But derandomization techniques are not easy to apply here because of the cardinality constraint, and can have a high computational cost. In this paper we present a deterministic max(d,8/9c)-approximation algorithm for the Densest k-Subgraph Problem (where d is the density of G). The complexity of our algorithm is only the one of linear programming. This result is obtained by using particular optimal solutions of a linear program associated with the classical 0-1 quadratic formulation of DSP.

Equipe: oc
Collaboration: LIPN


@article {
title="{A Deterministic Approximation Algorithm for the Densest k-Subgraph Problem}",
author="A. Billionnet and F. Roupin",
journal="International Journal of Operational Research",