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 \ge 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 \ge 2\) . For the second variant, which is NP-hard for \(k \ge 3\) , we present an approximation algorithm that achieves a factor of \(\frac{3}{7}\) . The approximation algorithm is obtained by showing that a related problem, that of finding k distinct densest subgraphs can be solved in polynomial time.
