Title: Top-k Overlapping Densest Subgraphs: Approximation and Complexity,
Abstract: 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 dens- est 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.