Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00491
Covering a Graph with Clubs
Vol. 23, no. 2, pp. 271-292, 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 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 -\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 $2|V|^{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
|