2026-07-26T23:12:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16960 2024-03-06T10:58:49Z ddc:004 open_access

On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations Blažej, Václav Choudhary, Pratibha Knop, Dušan Schierreich, Šimon Suchý, Ondřej Valla, Tomáš Traveling Salesperson Subset TSP Waypoint Routing Kernelization For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Václav Blažej and Pratibha Choudhary and Dušan Knop and Šimon Schierreich and Ondřej Suchý and Tomáš Valla 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.22 urn:nbn:de:0030-drops-169600 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.22 eng https://creativecommons.org/licenses/by/4.0/legalcode