Assignment problem based algorithms are impractical for the generalized TSP

Abstract

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.