Harry Potter is looking for a bowtruckle that is hiding in a graph and has made itself invisible. Harry tries to find the bowtruckle by casting the spell rivilio trullio while aiming his wand at a vertex of the graph. The first time he hits the bowtruckle it will stay invisible but move to a neighbouring vertex of the graph. However, Harry will not be able to notice this because the bowtruckle moves silently. The second time that Harry hits the bowtruckle it will become visible. Harry’s wand has just enough energy left to cast the spell rivilio trullio k times. Therefore, Harry wants to know whether he can choose at most k vertices of the graph such that he is sure that he will find the bowtruckle when he casts rivilio trullio on each of these vertices. Show that this problem is NP-complete.
I proved that the problem is NP, by showing it can be checked in polynomial time. Now I need to show its NP-Hard. To what problem can it be compared for reduction?