1. Covering with clubs: Complexity and approximability
- Author
-
Giancarlo Mauri, Florian Sikora, Italo Zoppis, Riccardo Dondi, Università degli Studi di Bergamo, Università degli studi di Bergamo (UniBG), Università degli Studi di Milano-Bicocca [Milano] (UNIMIB), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Iliopoulus, C, Leong, HW, Sung WK, Dondi, R, Mauri, G, Sikora, F, and Zoppis, I
- Subjects
Vertex (graph theory) ,graph algorithms ,FOS: Computer and information sciences ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Computer Science - Data Structures and Algorithms ,[INFO]Computer Science [cs] ,Data Structures and Algorithms (cs.DS) ,Graph algorithms ,approximation algorithms ,Mathematics ,021103 operations research ,Settore INF/01 - Informatica ,INF/01 - INFORMATICA ,Approximation algorithm ,Graph theory ,approximation complexity, cohesive subgraphs, graph covering ,s-Clubs ,010201 computation theory & mathematics ,Computer Science ,Algorithms ,Combinatorial optimization ,combinatorial optimization - Abstract
Finding cohesive subgraphs in a network is a well-known problem in graph theory. Several alternative formulations of cohesive subgraph have been proposed, a notable example being $s$-club, which is a subgraph where each vertex is at distance at most $s$ to the others. Here we consider the problem of covering a given graph with the minimum number of $s$-clubs. We study the computational and approximation complexity of this problem, when $s$ is equal to 2 or 3. First, 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., Accepted in IWOCA 2018
- Published
- 2018
- Full Text
- View/download PDF