Your friends at WebTech have recently been doing some consulting work for compan
ID: 3543845 • Letter: Y
Question
Your friends at WebTech have recently been doing some consulting work for companies that maintain large, publicly accessible website-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 website, which we will 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 will model these trails as directed paths p1,p2,...,pt in the graph G (i.e., each pi is a path in G). The company wants WebTech 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 with an advertisement? We'll call this the Strategic Advertising problem (SA) with input G, {pii=1,....t} , and k. Your friends figure tht a good algorithm for this will make them all rich; unfortunately, things are never quite this simple.
(a) Prove that SA is NP-Complete. (Hint: Recall the Vertex Cover Problem)
Explanation / Answer
You can reduce CLIQUE (G has a clique of size k) to KITE: given G=(V,E) and k, just build in polynomial time a new graph G? in this way: for each node vi add a tail of k new nodes.
If G? has a kite of size 2k then the G has a clique of size k (the kite without the tail). Added nodes cannot introduce new cliques on G?, so G contains exactly the same cliques of G?.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.