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 2/5.