Gutin, Gregory and Yeo, Anders (2003) Assignment problem based algorithms are impractical for the generalized TSP. Australasian Journal of Combinatorics, 27
Full text access: Open
In the Generalized Traveling Salesman Problem (GTSP), given a weighted complete digraph D and a partition V1 . . . Vk of the vertices of D, we are to find a minimum weight cycle containing exactly one (at least one) vertex from each set Vi, i = 1,... k. Assignment Problem based approaches are extensively used for the Asymmetric TSP. To use analogs of these approaches for the GTSP, we need to find a minimum weight 1-regular subdigraph that contains exactly one (at least one) vertex from each Vi. We prove that, unfortunately, the corresponding problems are NP-hard. In fact, we show the following stronger result: Let V = (D,A) be a digraph and let V1, V2, . . . Vk be a partition of V. The problem of checking whether D has a 1-regular digraph containing exactly one vertex from each V1, V2, . . . Vk is NP-complete even if |Vi| is less than or equal to 2 for every i = 1, 2, . . . k.
This is a Submitted version This version's date is: 2003 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/da644df6-dcc5-7fe3-0a82-14853739a3d2/3/
Deposited by Research Information System (atira) on 25-Jul-2012 in Royal Holloway Research Online.Last modified on 25-Jul-2012