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.
articolo
2024
Dondi, Riccardo; Popa, Alexandru
(2024). Covering a Graph with Densest Subgraphs [journal article - articolo]. In LA MATEMATICA. Retrieved from https://hdl.handle.net/10446/296086
File allegato/i alla scheda:
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/296086
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact