Theory of Computation

(a) Let SHORT-TRIP = { | G is an undirected graph and G contains a simple path of length at most k from node s to node t}. Show SHORT-TRIP ? P.

(b) Let LONG-TRIP = { | G is an undirected graph and G contains a simple path of length at least k from node s to node t}. Show LONG-TRIP is NP-complete. Hint: use UHAMPATH.