Covering a graph with clubs

Finding cohesive subgraphs in a network has been investigatSeveral alternative formulations of cohesive subgraph have been proposed, a notable one of them is s-club, which is a subgraph whose diameter is at most s. Here we consider a natral variant of the well-known Minimum Clique Cover problem, where we aim to cover a given graph with the minimum number of s-clubs, instead of cliques. We study the computational and approximation complexity of this problem, when s is equal to 2 or 3. We show that deciding if there exists a cover of a graph with three 2-clubs is NP-complete, and that deciding if there exists a cover of a graph with two 3-clubs is NP-complete. Then, we consider the approximation complexity of covering a graph with the minimum number of 2-clubs and 3-clubs. We show that, given a graph G = (V, E) to be covered, covering G with the minimum number of 2-clubs is not approximable within factor O(|V |1/2−ε), for any ε > 0, and covering G with the minimum number of 3-clubs is not approximable within factor O(|V |1−ε), for any ε > 0. On the positive side, we give an approximation algorithm of factor 2|V |1/2 log3/2 |V | for covering a graph with the minimum number of 2-clubs.