Find shortest path in undirected complete n-partite graph that visits each partition exactly once Disclaimer: I am no mathematician and will express the problem in a more verbal manner.
I am trying to find a solution algorithm for the graph problem visualized below. I have an undirected weighted complete n-partite graph (here tri-partite). Each partition has exactly two unconnected vertices (here indicated with a blue hull). Weighted edges exist between all vertices from different partitions (i.e. complete graph). Hence, a path visiting all partitions must always exist. All weights are $\geq 0$. I want to find the shortest path(s) that visits exactly one vertex in each partition. The edges and vertices for one possible shortest path in the toy example are marked in red. My concrete case is 20-partite (i.e. 40 vertices) as maximal size.


*

*Is there a special name for this problem?

*Does an algorithm exist that solves this problem?

*If not, is there a way to reformulate this problem into a known one?
Thanks!

 A: 
Is there a special name for this problem?

«In combinatorial optimization, the set TSP, also known as the generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the Traveling salesman problem (TSP) [Wik1], whereby it is required to find a shortest tour in a graph which visits all specified subsets of the vertices of a graph. The subsets of vertices must be disjoint». [Wik2] It is also known as the "travelling politician problem", which deals with "states" that have (one or more) "cities" and the salesman has to visit exactly one "city" from each "state". [Wik1]

Does an algorithm exist that solves this problem? If not, is there a way to reformulate this problem into a known one?

«The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons. Therefore, the set TSP is also NP-hard», [Wik2] so it should admit (known) algorithms of polynoimal computation complexity only in special cases. On the other hand, «Noon and Bean demonstrated that the generalized travelling salesman problem can be transformed into a standard travelling salesman problem with the same number of cities, but a modified distance matrix» [Wik1] . «There is a direct transformation for an instance of the set TSP to an instance of the standard asymmetric TSP. [BN] The idea is to first create disjoint sets and then assign a directed cycle to each set. The salesman, when visiting a vertex in some set, then walks around the cycle for free. To not use the cycle would ultimately be very costly. [Wik2] The obtained TSP can be solved with professional software such as Concorde.
Acknowledgement
The author thanks to Alexander Wolff from Würzburg University (Germany) for his kind help. 
References
[BN] James Bean, Charles Noon. An efficient transformation of the generalized traveling salesman problem (1993).
[Wik1] Wikipedia, Travelling salesman problem. 
[Wik2] Wikipedia, Set TSP problem.
