Exercise 12.7. Here we consider an extension of shortast (5,1)-walks where one has to visit a family of vertices specified by the input. The input consists of a directed graph G=(V,E) with positive edge lengths h:ER>0 as well as a list of vertices x1,,xkV. The high-level goal in both of the following problems is to compute the length of the shortest walk that visits all k vertices. 1. Suppose you are allowed to visit x1,,xk in any order. Consider the problem of computing the length of the shortest walk visiting all of x1,,xk in any order. (You may assume no vertices repeat in x1,,xk ) For this problem, either (a) design and analyze a polynomial time algorithm (the faster the better), or (b) prove that a polynomial time algorithm would imply a polynomial time algorithm for SAT