Your friends at WebExodus have recently been doing some consulting work for companies that maintain large, publicly accessible Web sites- contractual issues prevent them from saying which ones-and they ve come across the following Strategic Advertising Problem. A company comes to them with the map of a Web site, which we ll model as a directed graph G - (V, E). The company also provides a set of t trails typically followed by users of the site; we I model these trails as directed paths P1, P2, ..., Pt in the graph G (i.e., eachPt is a path in G). The company wants WebExodus to answer the following question for them: Given G, the paths (Pi), and a number k, is it possible to place advertisements on at most k of the nodes in G, so that each path Pi includes at least one node containing an advertisement? We Il call this the Strategic Advertising Problem, with input G, (Pi i-1,...,t}, and k. Your friends figure that a good algorithm for this will make them all rich; unfortunately, things are never quite this simple. (a) Prove that Strategic Advertising is NP-complete. (b) Your friends at WebExodus forge ahead and write a pretty fast algorithm S that produce:s yes/no answers to arbitrary instances of the Strategic Advertising Problem. You may assume that the algorithm S is always correct. Using the algorithm S as a black box, design an algorithm that takes input G, (Pi), and k as in part (a), and does one of the following two things: Outputs a set of at most k nodes in G so that each pathPt includes at least one of these nodes, or Outputs (correctly) that no such set of at most k nodes exists. Your algorithm should use at most a polynomial number of steps, together with at most a polynomial number of calls to the algorithm S