论文标题
在$ D $ -CLAW顶点删除问题上
On the $d$-Claw Vertex Deletion Problem
论文作者
论文摘要
令$ d $ -claw（或$ d $ -star）代表$ k_ {1，d} $，每个部分的完整两部分图和$ d \ ge 1 $顶点。 $ D $ -CLAW顶点删除问题，$ D $ -CLAW-VD，要求给定的图$ G $和整数$ K $，如果最多可以从$ g $中删除$ g $ g $，以至于所产生的图形没有$ d $ -cl-claw-claw作为诱导的子图。因此，1-Claw-VD和2-Claw-VD只是著名的顶点覆盖问题和群集顶点删除问题。在本文中，我们加强了硬度的结果。 Yannakakis，两分图上的节点 - 缺失问题，Siam J. Comput。 （1981）]，通过证明群集顶点删除在最高学位3的两部分图时仍然保持NP的结构。此外，对于每$ d \ ge 3 $，我们表明$ d $ -claw-vd即使仅限于最高度$ d $ d $的两分。这些硬度结果对于程度约束是最佳的。通过扩展硬度结果[F。 Bonomo-Braberman et al., Linear-Time Algorithms for Eliminating Claws in Graphs, COCOON 2020], we show that, for every $d\ge 3$, $d$-CLAW-VD is NP-complete even when restricted to split graphs without $(d+1)$-claws, and split graphs of diameter 2. On the positive side, we prove that $d$-CLAW-VD is在我们所谓的$ d $ block图上可求解的多项式求解，一类正确包含所有块图。该结果扩展了[Y.中的多项式时间算法。 Cao等人，弦图上的顶点缺失问题，理论。计算。科学。 （2018）]对于块图上的2卢比vd至$ d $ -claw-vd，用于所有$ d \ ge 2 $，并改善了F. Bonomo-Brabeman等人提出的多项式时间算法。对于（未加权）3-CLAW-VD在块图上至3块图。
Let $d$-claw (or $d$-star) stand for $K_{1,d}$, the complete bipartite graph with 1 and $d\ge 1$ vertices on each part. The $d$-claw vertex deletion problem, $d$-CLAW-VD, asks for a given graph $G$ and an integer $k$ if one can delete at most $k$ vertices from $G$ such that the resulting graph has no $d$-claw as an induced subgraph. Thus, 1-CLAW-VD and 2-CLAW-VD are just the famous VERTEX COVER problem and the CLUSTER VERTEX DELETION problem, respectively. In this paper, we strengthen a hardness result in [M. Yannakakis, Node-Deletion Problems on Bipartite Graphs, SIAM J. Comput. (1981)], by showing that CLUSTER VERTEX DELETION remains NP-complete when restricted to bipartite graphs of maximum degree 3. Moreover, for every $d\ge 3$, we show that $d$-CLAW-VD is NP-complete even when restricted to bipartite graphs of maximum degree $d$. These hardness results are optimal with respect to degree constraint. By extending the hardness result in [F. Bonomo-Braberman et al., Linear-Time Algorithms for Eliminating Claws in Graphs, COCOON 2020], we show that, for every $d\ge 3$, $d$-CLAW-VD is NP-complete even when restricted to split graphs without $(d+1)$-claws, and split graphs of diameter 2. On the positive side, we prove that $d$-CLAW-VD is polynomially solvable on what we call $d$-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in [Y. Cao et al., Vertex deletion problems on chordal graphs, Theor. Comput. Sci. (2018)] for 2-CLAW-VD on block graphs to $d$-CLAW-VD for all $d\ge 2$ and improves the polynomial-time algorithm proposed by F. Bonomo-Brabeman et al. for (unweighted) 3-CLAW-VD on block graphs to 3-block graphs.
