Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов

В работе изучается общая постановка обобщенной задачи коммивояжера (GTSP), в которой требуется построить кратчайший циклический маршрут, посещающий каждый элемент фиксированного разбиения множества вершин заданного взвешенного графа (именуемый кластером или мегаполисом) в единственной вершине. Обобщив классическое понятие пирамидального маршрута и введя в рассмотрение квази- и псевдопирамидальные маршруты для задачи GTSP, мы показали, что оптимальный $l$-квазипирамидальный и $l$-псевдопирамидальный маршруты в произвольной постановке задачи на $n$ вершинах и $k$ кластерах могут быть построены за время $O(4^l n^3)$ и $O(2^lk^{l+4}n^3)$ соответственно. Как следствие показано, что задача GTSP принадлежит классу FPT относительно параметризаций, задаваемых такими типами маршрутов. Кроме того, обоснована полиномиальная разрешимость геометрического подкласса задачи, известного в литературе как GTSP-GC, произвольная постановка которого стеснена дополнительным ограничением $H\leq 2$ на высоту решетки, определяющей кластеры.