论文标题
用于消除图中爪的线性时间算法
Linear-time Algorithms for Eliminating Claws in Graphs
论文作者
论文摘要
由于在仅限于无爪图的情况下，已经显示了许多NP完整的图形问题可溶可解的多项式时间，因此我们研究了确定给定图与无爪图的距离的问题，将其视为措施。无爪顶点删除（CFVD）包括确定要从图中删除的最小顶点数量，以使所得图无爪。尽管CFVD一般是NP纯的，并且识别无爪图仍然是一个挑战，在该图形$ G $的当前最佳算法具有与矩阵乘法最佳算法的相同运行时间，但我们呈现加权块上的CFVD的线性时间算法，并具有加权块图和带有限制性树木的加权图形的CFVD。此外，我们证明可以通过森林上的简单算法在线性时间解决此问题，并确定完整$ k $ are树的确切值。另一方面，我们表明，即使输入图是一个拆分图，无爪顶点删除也是NP完成的。我们还表明，假设唯一的游戏猜想，这个问题很难在任何不变因素内都比$ 2 $好。
Since many NP-complete graph problems have been shown polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination as measure. CLAW-FREE VERTEX DELETION (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free. Although CFVD is NP-complete in general and recognizing claw-free graphs is still a challenge, where the current best algorithm for a graph $G$ has the same running time of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem can be solved in linear time by a simpler algorithm on forests, and we determine the exact values for full $k$-ary trees. On the other hand, we show that CLAW-FREE VERTEX DELETION is NP-complete even when the input graph is a split graph. We also show that the problem is hard to approximate within any constant factor better than $2$, assuming the Unique Games Conjecture.
