论文标题
独立集的1-扩展性
1-Extendability of independent sets
论文作者
论文摘要
在70年代，Berge引入了1延伸图（也称为B-Graphs），这是每个顶点属于最大独立集的图形。在无线网络设计中的应用中，我们研究了1-扩展性的计算复杂性，这是确定图形是否可扩展的问题。我们表明，通常不能以$ 2^{o（n）} $时间来解决1-可扩展性，假设指数时间假设，其中$ n $是输入图的顶点的数量，并且它仍然在子立管平面图中仍然是NP-HARD，则在单位磁盘和单位磁盘图中（这是无线网络的自然模型）。尽管1-扩展性似乎非常接近找到独立的最大大小集（又称最大独立集）的问题，但我们表明，有趣的是，存在最大独立集为NP-HARD的1延伸图。最后，我们研究了1-扩展性的参数化版本。
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.
