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≥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≥2. For the second variant, which is NP-hard for k≥3, we present an approximation algorithm that achieves a factor of 37. The approximation algorithm is obtained by showing that a related problem, that of finding k distinct densest subgraphs can be solved in polynomial time.
(2024). Covering a Graph with Densest Subgraphs [journal article - articolo]. In LA MATEMATICA. Retrieved from https://hdl.handle.net/10446/296086
Covering a Graph with Densest Subgraphs
Dondi, Riccardo;
2024-01-01
Abstract
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≥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≥2. For the second variant, which is NP-hard for k≥3, we present an approximation algorithm that achieves a factor of 37. The approximation algorithm is obtained by showing that a related problem, that of finding k distinct densest subgraphs can be solved in polynomial time.File | Dimensione del file | Formato | |
---|---|---|---|
LaMatematica.pdf
Solo gestori di archivio
Versione:
publisher's version - versione editoriale
Licenza:
Licenza default Aisberg
Dimensione del file
396.82 kB
Formato
Adobe PDF
|
396.82 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo