G = (V;E) is an n-vertex undirected graph, and every vertex has a coupon on it. There are k kinds of coupons.
You are initially sitting on the vertex s 2 V . You have a total of k steps available to you,and in each step you can move from your current vertex to an adjacent vertex and collect the coupon on that vertex. Your goal is to collect one coupon of each kind and return back to s.
Give a poly(n; 2k)-time algorithm to determine whether this is possible, and if so, which steps you should take in order to achieve this. (Note that an nO(k) algorithm is trivial.)