Bazgan, Cristina and Pontoizeau, Thomas and Tuza, Zsolt (2019) Finding a potential community in networks. THEORETICAL COMPUTER SCIENCE, 769. pp. 32-42. ISSN 0304-3975
|
Text
Bazgan-Pontoi-Tuza-Finding-a-potential-community.pdf Download (219kB) | Preview |
Abstract
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 it with the complexity of maximum independent set. We prove that this problem is NP-hard on apex graphs, APX-hard on line graphs, not n(1/2-epsilon)-approximable on bipartite graphs and not n(1-epsilon)-approximable on split graphs, while it is polynomial-time solvable on graphs of bounded degree and their complements, graphs of bounded treewidth, planar graphs, (C-3, C-6)-free graphs, threshold graphs, interval graphs and cographs. (C) 2018 Elsevier B.V. All rights reserved.
| Item Type: | Article |
|---|---|
| Additional Information: | Funding Agency and Grant Number: National Research, Development and Innovation Office - NKFIH [SNN 116095] Funding text: Research of Zsolt Tuza was supported in part by the National Research, Development and Innovation Office - NKFIH under the grant SNN 116095. |
| Uncontrolled Keywords: | ALGORITHM; GRAPHS; COMPLEXITY; GRAPH; Independent set; completeness; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 16 Jan 2020 12:53 |
| Last Modified: | 16 Jan 2020 12:53 |
| URI: | http://real.mtak.hu/id/eprint/105505 |
Actions (login required)
 |
Edit Item |
