Question

Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph
induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v that is an element of S provided
that {u,v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of
G, that is G[V - K] has no edges. prove that finding the smallest killer set of G is an NP-hard using the vertex cover problem .

Answer 1

Reduction is very simple. If we have algorithm which given the graph G=(V,E) returns the smallest killer set of G then we can solve the problem of finding minimum vertex cover which is NP-hard problem.

Yes every killer set K is vertex cover set also because K is the killer set if and only if every edge in G=(V,E) is incident on some vertex in set K and since every edge in E is incident on some vertex in E, so E is vertex cover also .

Hence finding smallest killer set will be equivalent to finding minimum vertex cover in just polynomial time reduction and since minimum vertex cover finding is NP-hard, so smallest killer set finding is also NP-hard.

Please comment for any clarification.