Covering a Graph with Clubs

Finding cohesive subgraphs in a network has been investigatSeveral al-ternative formulations of cohesive subgraph have been proposed, a notableone of them iss-club, which is a subgraph whose diameter is at mosts.Here we consider a natral variant of the well-knownMinimum Clique Coverproblem, where we aim to cover a given graph with the minimum num-ber ofs-clubs, instead of cliques. We study the computational and ap-proximation complexity of this problem, whensis equal to 2 or 3. Weshow that deciding if there exists a cover of a graph with three 2-clubsis NP-complete, and that deciding if there exists a cover of a graph withtwo 3-clubs is NP-complete. Then, we consider the approximation com-plexity of covering a graph with the minimum number of 2-clubs and3-clubs. We show that, given a graphG= (V, E) to be covered, cover-ingGwith the minimum number of 2-clubs is not approximable withinfactorO(|V|1/2−ε), for anyε >0, and coveringGwith the minimumnumber of 3-clubs is not approximable within factorO(|V|1−ε), for anyε >0. On the positive side, we give an approximation algorithm of fac-tor 2|V|1/2log3/2|V|for covering a graph with the minimum number of2-clubs.