The claw in a graph $G(V,E)$ consists of a vertex $v\in V$, and it's three neighbours - $\{x_1,x_2,x_3\}\in V\setminus \{v\}$, if $\{x_1,x_2,x_3\}$ form an independent set in $G$.

The problem asks us to prove that the following problem is NP-complete:

Is there a set of $k$ vertices $S$, such that $G(V\setminus S, E)$ is claw-free?

It is simple to prove that problem is in NP - we can check in polynomial time whether the graph is claw-free after removing $k$ vertices. So now the only thing needed is to find a reduction from some known NP-complete problem to this one. I've been stuck on this problem for 2 weeks - I've thought about reducing VERTEX COVER, but after fiddling with it I think this may be a dead end. I will be grateful for any tips, that would point me in the right direction.


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.