A DETERMINISTIC APPROXIMATION ALGORITHM FOR THE DENSEST K-SUBGRAPH PROBLEM

Abstract. 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 prob-lem 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> 1). But derandomization techniques are c 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