Covering a Graph with Clubs - Dondi, Riccardo; Mauri, Giancarlo; Sikora, Florian; Zoppis, Italo (Journal of Graph Algorithms and Applications, 2019)
Finding cohesive subgraphs in a network has been investigated in many network mining applications.Several 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 natural variant of the well-knownMinimum Clique Cover problem, where we aim to covera 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 isnot approximable within factor $O(|V|^{1/2 -ε})$, for any $ε>0$, and covering $G$ with the minimum number of $3$-clubs isnot approximable within factor $O(|V|^{1 -ε})$, for any $ε>0$.On the positive side, we give an approximationalgorithm of factor $2|V|^{1/2}\log^{3/2} |V|$ for covering a graph with the minimum number of $2$-clubs.