  Computing cohesive subgraphs is a central problem in graph theory. While many
formulations of cohesive subgraphs lead to NP-hard problems, finding a densest
subgraph can be done in polynomial time. As such, the densest subgraph model
has emerged as the most popular notion of cohesiveness. Recently, the data
mining community has started looking into the problem of computing k densest
subgraphs in a given graph, rather than one, with various restrictions on the
possible overlap between the subgraphs. However, there seems to be very little
known on this important and natural generalization from a theoretical
perspective. In this paper we hope to remedy this situation by analyzing three
natural variants of the k densest subgraphs problem. Each variant differs
depending on the amount of overlap that is allowed between the subgraphs. In
one extreme, when no overlap is allowed, we prove that the problem is NP-hard
for k >= 3. On the other extreme, when overlap is allowed without any
restrictions and the solution subgraphs only have to be distinct, we show that
the problem is fixed-parameter tractable with respect to k, and admits a PTAS
for constant k. Finally, when a limited of overlap is allowed between the
subgraphs, we prove that the problem is NP-hard for k = 2.
