Name
Abstract | ||
|---|---|---|
In the 70s, 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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/978-3-031-06678-8_13 | International Workshop on Combinatorial Algorithms (IWOCA) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pierre Bergé | 1 | 0 | 0.68 |
| Anthony Busson | 2 | 0 | 2.03 |
| Carl Feghali | 3 | 26 | 7.20 |
| Rémi Watrigant | 4 | 0 | 1.69 |