  A central problem in graph mining is finding dense subgraphs, with several
applications in different fields, a notable example being identifying
communities. While a lot of effort has been put on the problem of finding a
single dense subgraph, only recently the focus has been shifted to the problem
of finding a set of densest subgraphs. Some approaches aim at finding disjoint
subgraphs, while in many real-world networks communities are often overlapping.
An approach introduced to find possible overlapping subgraphs is the Top-k
Overlapping Densest Subgraphs problem. For a given integer k >= 1, the goal of
this problem is to find a set of k densest subgraphs that may share some
vertices. The objective function to be maximized takes into account both the
density of the subgraphs and the distance between subgraphs in the solution.
  The Top-k Overlapping Densest Subgraphs problem has been shown to admit a
1/10-factor approximation algorithm. Furthermore, the computational complexity
of the problem has been left open. In this paper, we present contributions
concerning the approximability and the computational complexity of the problem.
For the approximability, we present approximation algorithms that improves the
approximation factor to 1/2 , when k is bounded by the vertex set, and to 2/3
when k is a constant. For the computational complexity, we show that the
problem is NP-hard even when k = 3.
