Given an undirected graph with n vertexes, each edge with a cost. Given some pairs [a,b] meaning you should carry something from a to b. Can this get solved in 2^n*Poly(n) time?
No extra requirement on number of edges and pairs but they're automatically bounded by n^2