On minimum $t$-claw deletion in split graphs

For $t\ge 3$, $K_{1,t}$ is called $t$-claw. In minimum $t$-claw deletion problem ($\mathtt{\text{Min-}}t\mathtt{\text{-Claw-Del}}$), given a graph $G=(V,E)$, it is required to find a vertex set $S$ of minimum size such that $G[V\setminus S]$ is $t$-claw free. In a split graph, the vertex set is partitioned into two sets such that one forms a clique and the other forms an independent set. Every $t$-claw in a split graph has a center vertex in the clique partition. This observation motivates us to consider the minimum one-sided bipartite $t$-claw deletion problem ($\mathtt{\text{Min-}}t\mathtt{\text{-OSBCD}}$). Given a bipartite graph $G=(A\cup B,E)$, in $\mathtt{\text{Min-}}t\mathtt{\text{-OSBCD}}$ it is asked to find a vertex set $S$ of minimum size such that $G[V\setminus S]$ has no $t$-claw with the center vertex in $A$. A primal-dual algorithm approximates $\mathtt{\text{Min-}}t\mathtt{\text{-OSBCD}}$ within a factor of $t$. We prove that it is $\text{UGC}$-hard to approximate with a factor better than $t$. We also prove it is approximable within a factor of 2 for dense bipartite graphs. By using these results on $\mathtt{\text{Min-}}t\mathtt{\text{-OSBCD}}$, we prove that $\mathtt{\text{Min-}}t\mathtt{\text{-Claw-Del}}$ is $\text{UGC}$-hard to approximate within a factor better than $t$, for split graphs. We also consider their complementary maximization problems and prove that they are $\text{APX}$-complete.