4. (Exercise 8.37 from Kleinberg & Tardos) There are those who insist that the i

Question

4. (Exercise 8.37 from Kleinberg & Tardos) There are those who insist that the initial working title for Episode XXVII of the Star Wars series was "P NP" _ but this is surely apocryphal In any case, if you're so inclined, it's easy to find NP-complete problems lurking just below the surface of the original Star Wars movies Consider the problem faced by Luke, Leia, and friends as they tried to make their way from the Death Star back to the hidden Rebel base. We can view the galaxy as an undirected graph G- (V, E), where each node is a star system and an edge (u,v) indicates that one can travel directly from u to v. The Death Star is represented by a node s, the hidden Rebel base by a node t. Certain edges in this graph represent longer distances than others; thus each edge e has an integer length le 2 0. Also, certain edges represent routes that are more heavily patrolled by evil Imperial spacecraft; so each edge e also has an integer risk re 2 0, indicating the expected amount of damage incurred from spcial-effects-intensive space battles if one traverses this edge. It would be safest to travel through the outer rim of the galaxy, from one quiet star system to another; but then one's ship would run out of fuel long before getting to its destination. Alternately, it would be quickest to plunge through the cosmopolitan core of the galaxy; but then there would be far too many Imperial spacecraft to deal with. In general, for any path P from s to t, we can define its total length to be the sum of the lengths of all its edges; and we can define its total risk to be the sum of the risks of all its edges So Luke, Leia and company are looking at a complex type of shortest-path problem in this graph: they need to get from s to t along a path whose total length and total risk are both reasonably small. In concrete terms, we can phrase the Galactic Shortest-PathProblem as follows: Given a setup as above, and integer bounds L and R, is there a path from s to t whose total length is at most L, and whose total risk is at most R? Prove that Galactic Shortest Path is NP-complete.

Explanation / Answer

This problem is in NP. To check a proposed path P, we just check that it has length at most L and risk value at most R.

We will reduce this to Set Partition Problem which is whether the numbers from a set S can be partitioned into two sets A and B = S A such that sum of set A and B is equal. This problem is NP-complete and we will try to reduce our problem into this problem in polynomial time to prove that Galactic shortest path is NP-complete.

To set this up as a path problem we take a directed path (with end vertices s and t) with n arcs, one for each integer. We now make two copies of each arc i. The first copy has length xi and risk value 0; the second copy has length 0 and risk value xi. So any s t path P in G uses exactly one the type i arcs. Let A be the set of integers where we use their first copy.  Thus the length of the path is Sum of all xi belonging to A. the risk of this path is risk values on those integers where we use the second copy of their arcs, so the risk is Sum of all xi belonging to B where B = S-A. So set R = L = (.5) * (sum of all xi) . Then we have a path of length at most L and risk at most R if an only if we have a valid partition. This is a polynomial reduction.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.