Thumbnail - Request a copy

On the complexity of finding a potential community

Bazgan, Cristina; Pontoizeau, Thomas; Zsolt, Tuza (2017), On the complexity of finding a potential community, in Fotakis, Dimitris; Pagourtzis, Aris; Vangelis Th., Paschos, Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), Springer International Publishing : Cham, p. 80-91. 10.1007/978-3-319-57586-5_8

Type
Communication / Conférence
Date
2017
Conference title
10th International Conference on Algorithms and Complexity (CIAC 2017)
Conference date
2017-05
Conference city
Athens
Conference country
Greece
Book title
Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017)
Book author
Fotakis, Dimitris; Pagourtzis, Aris; Vangelis Th., Paschos
Publisher
Springer International Publishing
Published in
Cham
ISBN
978-3-319-57585-8
Number of pages
486
Pages
80-91
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pontoizeau, Thomas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Zsolt, Tuza
Department of Computer Science - University of Pannonia [DCS]
Abstract (EN)
An independent 2-clique of a graph is a subset of vertices that is an independent set and such that any two vertices inside have a common neighbor outside. In this paper, we study the complexity of finding an independent 2-clique of maximum size in several graph classes and we compare its complexity with the complexity of maximum independent set. We prove that this problem is NP-hard on apex graphs, APX-hard on line graphs, not n1/2−ϵ-approximable on bipartite graphs and not n1−ϵ-approximable on split graphs, while it is polynomial-time solvable on graphs of bounded degree and their complements, graphs of bounded treewidth, planar graphs, (C3,C6)-free graphs, threshold graphs, interval graphs and cographs.
Subjects / Keywords
Combinatorial optimization; Complexity; Algorithm; Independent set; Inapproximability; Approximation; Partition