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 ll 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 ll 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 produces 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.
We need at least 10 more requests to produce the solution.
0 / 10 have requested this problem solution
The more requests, the faster the answer.