Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00491
Covering a Graph with Clubs
Vol. 23, no. 2, pp. 271292, 2019. Regular paper.
Abstract 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 wellknown
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 NPcomplete, and that
deciding if there exists a cover
of a graph with two $3$clubs is NPcomplete.
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 \varepsilon})$,
for any $\varepsilon>0$, and
covering $G$ with the minimum number of $3$clubs is
not approximable within factor $O(V^{1 \varepsilon})$, for any $\varepsilon>0$.
On the positive side, we give an approximation
algorithm of factor $2V^{1/2}\log^{3/2} V$ for covering
a graph with the minimum number of $2$clubs.

Submitted: September 2018.
Reviewed: February 2019.
Revised: February 2019.
Accepted: March 2019.
Final: March 2019.
Published: April 2019.
Communicated by
Paolo Ferragina

Journal Supporters
