1
$\begingroup$

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.

$\endgroup$

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.