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.


  • $\begingroup$ Hi Tami. Welcome to CS.stackexchange. The question is interesting. However, you should cite the original source of this problem (see help). $\endgroup$ – Inuyasha Yagami Jun 14 at 6:51
  • $\begingroup$ And, it is unlikely that you will receive help unless you mention what you have tried so far. $\endgroup$ – Inuyasha Yagami Jun 14 at 6:52
  • $\begingroup$ Well its a question from parameterized algorithms book.. we learned some techniques but can think about something specificaly. $\endgroup$ – Tami H Jun 14 at 11:11
  • $\begingroup$ 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? $\endgroup$ – Inuyasha Yagami Jun 14 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.