Problem 1 In one of the national parks the park administration wants to set up warning signs to inform tourists that they should check themselves for ticks after their hike. The park has a number of recommended routes, each of which touch some points of interest (POI). Different routes may contain the same POI. The signs will be placed at the POIs. The park wants to put up as few signs as possible, but in such a way that each route contains at least one sign. There are a total of n POIs and m routes.

(a) (5 points) Assume that you are given a "black-box" machine that can answer certain questions instantaneously. You can post to it the routes (as POI sequences) and a number k, and then the machine will output "yes" if there is a set of k locations for the signs so that each route contains some. Otherwise it returns "no". (It will not tell you the exact locations though.) Show an algorithm that can use polynomial number of calls to this machine and finds the minimum number k of signs required.

(b) (10 points) In class, you have learned about a problem called the set cover problem. Show that the sign placement problem is equivalent to the set cover problem, in the following way. Give a reduction of the sign placement problem to the set cover problem, and also a reduction from of the set cover problem to the sign placement problem.