Solvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours

We consider the general setting of the Generalized Traveling Salesman Problem (GTSP), where, for a given weighted graph and a partition of its nodes into clusters (or megalopolises), it is required to find a cheapest cyclic tour visiting each cluster exactly once. Generalizing the classical notion of pyramidal tour, we introduce quasi- and pseudopyramidal tours for the GTSP and show that, for an arbitrary instance of the problem with $n$ nodes and $k$ clusters, optimal $l$-quasi-pyramidal and $l$-pseudopyramidal tours can be found in time $O(4^l n^3)$ and $O(2^lk^{l+4}n^3)$, respectively. As a consequence, we prove that the GTSP belongs to the class FTP with respect to parametrizations given by such types of routes. Furthermore, we establish the polynomial-time solvability of the geometric subclass of the problem known in the literature as GTSP-GC, where an arbitrary statement is subject to the additional constraint $H\le 2$ on the height of the grid defining the clusters.