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 youre so inclined, its 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 `e 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 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 ones 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.