Covering a Graph with Densest Subgraphs

Finding densest subgraphs is a fundamental problem in graph mining, with several applications in different fields. In this paper, we consider two variants of the problem of covering a graph with k densest subgraphs, where k≥2. The first variant aims to find a collection of k subgraphs of maximum density, the second variant asks for a set of k subgraphs such that they maximize an objective function that includes the sum of the subgraphs densities and a distance function, in order to differentiate the computed subgraphs. We show that the first variant of the problem is solvable in polynomial time, for any k≥2. For the second variant, which is NP-hard for k≥3, we present an approximation algorithm that achieves a factor of 37. The approximation algorithm is obtained by showing that a related problem, that of finding k distinct densest subgraphs can be solved in polynomial time.