Covering a graph with densest subgraphs (Q6659505)

Finding cohesive subgraphs is fundamental in graph mining and graph theory. A number of models of cohesive subgraphs exist in the literature. Compared to other models, the densest subgraph has the advantage of being computed in polynomial time. The computational tractability and the natural definition of density have led to a prominent position in graph mining. Several real-world networks contain many cohesive groups that may share common elements, like hubs, usually belonging to many communities. The authors in this paper following an approach proposed by \textit{P. Rozenshtein} et al. [``Finding events in temporal networks: segmentation meets densest subgraph discovery'', Knowl. Inf. Syst. 62, No. 4, 1611--1639 (2020; \url{doi.org/10.1007/s10115-019-01403-9})] consider the problem of finding a collection of \(k\)-dense subgraphs that cover the input graph for \(k\) greater than or equal to 2. They consider two variants of the problem. In the first variant, the objective function is the sum of the densities of the \(k\) subgraphs, without any constraints except that they must cover the input graph. The second variant, similar to the objective function, includes both the sum of the densities of the \(k\) subgraphs and a distance function, to differentiate the subgraphs included in a solution. To provide an approximation algorithm for the second variant of the covering problem, the authors consider the problem of finding \(k\)-densest distinct subgraphs, where the input graph is not required to be covered. They show that the problem of finding \(k\)-densest distinct subgraphs is solvable in polynomial time. The article provides valuable algorithmic insights. Notably, the authors demonstrate that the first variant of the problem is solvable in polynomial time for any \(k\), offering an efficient solution for finding a collection of \(k\) subgraphs with maximum density. On the other hand, recognizing the NP-hard nature of the second variant for certain values of \(k\), they propose an approximation algorithm that achieves a factor of 3/7. This algorithmic contribution addresses the practical challenges associated with solving the problem in scenarios where exact solutions are computationally infeasible. They also raise some interesting open problems in the end for other researchers in this area.