I will rate asap. Thx

In the lecture we saw that given a complete graph K,,-(V. E) with edge cost cij 0 for {i, j} E E one can compute a minimum cost TSP tour in time 0(2"n3) using dynamic programming. Here, we want to consider a variant of this problem: INPUT: Complete graph K,,-(V. E) on n vertices with edge cost cij0 (for {i, j} E) and a parameter m { l ,.. . ,n) GoAL: Find a minimum cost circuit in K, that connects exactly m nodes Give an algorithm (based on the dynamic program for TSP) that solves the problem. What is the running time of your algorithm? (a straightforward solution would get you O(32") and O(n") which is better if m is a lot smaller than n? In the lecture we saw that given a complete graph K,,-(V. E) with edge cost cij 0 for {i, j} E E one can compute a minimum cost TSP tour in time 0(2"n3) using dynamic programming. Here, we want to consider a variant of this problem: INPUT: Complete graph K,,-(V. E) on n vertices with edge cost cij0 (for {i, j} E) and a parameter m { l ,.. . ,n) GoAL: Find a minimum cost circuit in K, that connects exactly m nodes Give an algorithm (based on the dynamic program for TSP) that solves the problem. What is the running time of your algorithm? (a straightforward solution would get you O(32") and O(n") which is better if m is a lot smaller than n