Relationships between Problems Sometimes small differences in a problem specification can make a big difference in complexity. For example, suppose you use a graph of nodes representing cities and weighted links between the nodes representing the distance via the best road traveling directly between the cities. Consider these problems The Single Pair Shortest Paths problem: what is the shortest path between a single pair of vertices (from one start vertex to one destination vertex) in the weighted graph? The Single Source Shortest Paths problem: what is the shortest path from one vertex to all the other vertices in a weighted graph? The All Pairs Shortest Paths problem: what is the shortest path from every vertex to all of the other vertices in a weighted graph? The Traveling Salesman problem: what is the shortest path that starts at a given vertex in a weighted graph and visits all of the other vertices once before returning to the start vertex? Questions: 1. How do these problems differ from each other? Are there any pairs A and B where B is a special case of A, so solving A ecessarilv solves B? 2. Which do you think are easier and which are harder? Which are tractable (e.g., can be computed in polynomial time) and which are potentially intractable (e.g., require exponential time), and why do you think so