Given a weighted undirected graph G = (V, E) and a set of nodes P and a starting node S and subset of nodes P_S.
I want to find the minimum weight circuit in this graph G such that it contains ALL the nodes in P_S. The circuit is allowed to backtrack (i.e. there could be a segment where it's A->B->C->B->A).
We'd thought about relating this to the TSP, but it's slightly different since we're trying to in fact get a circuit, and it's allowed to backtrack. We also considered using Dijkstra's to find the shortest paths between all the nodes that we need (the starting nodes and those in P_S), but that returns a tree which is not a circuit.
How can we find such a circuit?
