Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the $d$-Claw Vertex Deletion Problem   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.

16
The categories of this paper are: stat
11
The categories of this paper are: hep-lat
3
The categories of this paper are: physics
30
The categories of this paper are: q-alg
14
The categories of this paper are: math-ph
33
The categories of this paper are: plasm-ph
10
The categories of this paper are: q-bio
31
The categories of this paper are: ao-sci
9
The categories of this paper are: nlin
6
The categories of this paper are: astro-ph
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th
18
The categories of this paper are: econ
23
The categories of this paper are: solv-int
4
The categories of this paper are: cond-mat
34
The categories of this paper are: chem-ph