PLEASE EXPLAIN AS MUCH AS POSSIBLE. AND THIS ONE QUESTION WITH TWO PARTS. SO ANSWER BOTH PARTS.

2. (25%) In a board game, the Dark Lord reigns a domain consisting of locations that can be occupied by either playable characters or buildings. The Dark Lord wants to ensure that heros or heroines cannot enter into his domain without detection. To that end, he builds watchtowers at selected locations. The pressing problem is this: Powerful as he is, the Dark Lord only has enough funds to build k watchtowers. Now he needs to be strategic in choosing where to place his watchtowers. When he builds a watchtower at a certain location, both that location and some other nearby locations are considered "watched": when a hero or heroine lands on a "watched location, that event will be reported to the Dark Lord. In formal terms, the Dark Lord's domain can be modelled as an undirected graph, in which every vertex corresponds to a location, and there is an edge uv between locations u and v when there is unobstructed line of sight between them. In other words, if a watchtower is placed at a location u, then both u and all locations adjacent to u are considered "watched. For example, placing watchtowers at vertices 2 and 6 is sufficient to render every vertex "watched." 1 2 3 Z 4 The Watchtower Placement problem is the following decision problem. 1 Question: Given an undirected graph G = (V, E) and a positive integer k, does there exist a subset U of V such that |U|