# Claw-free graph - linear kernel

I'm having a hard time solving the problem below:

In Claw-free problem, we are given a graph $$G$$ and $$k$$, and the objective is to decide whether there exists a subset $$S \subseteq V (G)$$ of size at most $$k$$ such that $$G \setminus S$$ does not contain any $$3$$-star (known also as a claw) as a subgraph. Design an $$O(k)$$-vertex kernel for Claw-free problem. There's a hint which says we can use a $$4$$-approximation polynomial-time algorithm for $$4$$-Hitting Set as a black box.

Thanks!!!

• Hi Tami. Welcome to CS.stackexchange. The question is interesting. However, you should cite the original source of this problem (see help). – Inuyasha Yagami Jun 14 at 6:51
• And, it is unlikely that you will receive help unless you mention what you have tried so far. – Inuyasha Yagami Jun 14 at 6:52
• Well its a question from parameterized algorithms book.. we learned some techniques but can think about something specificaly. – Tami H Jun 14 at 11:11
• Hi Tami. I have a few ideas; however, I couldn't solve the problem. I also want to know the solution. So, I will perhaps write a different question with some ideas that I have tried. I couldn't find this problem in the "Parameterized Algorithms" book of Cygan et al. Can you please share the exact reference of this problem? – Inuyasha Yagami Jun 14 at 14:16