Back to Search
Start Over
1-Extendability of Independent Sets.
- Source :
-
Algorithmica . Mar2024, Vol. 86 Issue 3, p757-781. 25p. - Publication Year :
- 2024
-
Abstract
- In the 70 s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in the design of wireless networks, we study the computational complexity of 1-extendability, the problem of deciding whether a graph is 1-extendable. We show that, in general, 1-extendability cannot be solved in 2 o (n) time assuming the Exponential Time Hypothesis, where n is the number of vertices of the input graph, and that it remains NP-hard in subcubic planar graphs and in unit disk graphs (which is a natural model for wireless networks). Although 1-extendability seems to be very close to the problem of finding an independent set of maximum size (a.k.a.Maximum Independent Set), we show that, interestingly, there exist 1-extendable graphs for which Maximum Independent Set is NP-hard. Finally, we investigate a parameterized version of 1-extendability. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 86
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 175983329
- Full Text :
- https://doi.org/10.1007/s00453-023-01138-8