On the tractability of finding disjoint clubs in a network

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.