We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t≥2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s=2, t=3 and r=|V|. Moreover, we show that the problem is polynomial-time solvable when s≥4, t=3 and r=|V|, and when s≥3, t=2 and r=|V|. Finally, for s≥2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices.
(2019). On the tractability of finding disjoint clubs in a network [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from http://hdl.handle.net/10446/150297
On the tractability of finding disjoint clubs in a network
Dondi, Riccardo;
2019-01-01
Abstract
We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t≥2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s=2, t=3 and r=|V|. Moreover, we show that the problem is polynomial-time solvable when s≥4, t=3 and r=|V|, and when s≥3, t=2 and r=|V|. Finally, for s≥2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices.File | Dimensione del file | Formato | |
---|---|---|---|
TCS2019.pdf
Solo gestori di archivio
Versione:
publisher's version - versione editoriale
Licenza:
Licenza default Aisberg
Dimensione del file
331.81 kB
Formato
Adobe PDF
|
331.81 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo