Geodesic
Covering a Graph with Clubs
Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 271-292.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00491
Keywords: Clubs, Graph Partition, Approximation, Complexity 
@article{JGAA_2019_23_2_a5,
     author = {Riccardo Dondi and Giancarlo Mauri and Florian Sikora and Italo Zoppis},
     title = {Covering a {Graph} with {Clubs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {271--292},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2019},
     doi = {10.7155/jgaa.00491},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00491/}
}
TY  - JOUR
AU  - Riccardo Dondi
AU  - Giancarlo Mauri
AU  - Florian Sikora
AU  - Italo Zoppis
TI  - Covering a Graph with Clubs
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 271
EP  - 292
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00491/
DO  - 10.7155/jgaa.00491
LA  - en
ID  - JGAA_2019_23_2_a5
ER  - 
%0 Journal Article
%A Riccardo Dondi
%A Giancarlo Mauri
%A Florian Sikora
%A Italo Zoppis
%T Covering a Graph with Clubs
%J Journal of Graph Algorithms and Applications
%D 2019
%P 271-292
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00491/
%R 10.7155/jgaa.00491
%G en
%F JGAA_2019_23_2_a5
Riccardo Dondi; Giancarlo Mauri; Florian Sikora; Italo Zoppis. Covering a Graph with Clubs. Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 271-292. doi : 10.7155/jgaa.00491. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00491/

Cité par Sources :