5
$\begingroup$

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.

  1. Is there a special name for this problem?
  2. Does an algorithm exist that solves this problem?
  3. If not, is there a way to reformulate this problem into a known one?

Thanks!

enter image description here

$\endgroup$
4
  • $\begingroup$ Your problem apppears to be a multi-paritite variation (except your problem doesn't require a return to the starting part) of the Traveling Salesman Problem (en.wikipedia.org/wiki/Travelling_salesman_problem), which is known to be NP-hard. In practical terms, that means that for your $20$-partite problem, there's no known fast algorithm. $\endgroup$
    – quasi
    May 30 '20 at 18:58
  • $\begingroup$ @quasi: Can you outline how can one reformulate it as TSP? I know that one can reformulate finding a Hamiltonian path using the TSP formulation with a dummy vertex. But I was not able to do that here in the k-partite case. Do you know how? PS. no need for fast solving. Time is no hard constraint here. $\endgroup$ May 30 '20 at 19:00
  • $\begingroup$ I don't immediately see how to recast your problem as an instance of TSP, but your problem is clearly in the same vein, so I suggest looking into how the TSP is dealt with in practice. $\endgroup$
    – quasi
    May 30 '20 at 19:07
  • 1
    $\begingroup$ There is some literature on TSP and Hamiltonian paths in multipartite graphs, However, it did not help me, as in my case, I do not need a full path or cycle, but exactly one visit to each partition, which means doing only have the TSP journey or half the path. So the structure of the problem is related but also quite different. Also, I am hoping to cast this into a known problem with available algorithms in R or Python, as doing it myself might be beyond my capabilities. $\endgroup$ May 30 '20 at 20:33
2
+50
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ thanks or the answer! I will need a few days to read it and check if it covers my case. :) $\endgroup$ Jun 4 '20 at 8:21
  • 1
    $\begingroup$ Thanks! The exact name of the problem is the "Equality Generalized TSP" (E-GTPS). It has been shown that it can be transformed into the standard TSP. From there I can get the shortest Hamiltonian path, I think. Also, there is a solver (more here: webhotel4.ruc.dk/~keld/research/GLKH/GLKH_Report.pdf). Unfortunately, I have not found an R or python package yet. Any hints welcome! :) $\endgroup$ Jun 10 '20 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.