On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations

We investigated kernels for TSP and a related problem called Waypoint routing (WRP) – a variant of TSP where one needs to only visit a subset of vertices (subset TSP) and edges have capacities for the maximum number of their traversal within the solution. Compared to the classical TSP where one may create edges that represent shortest paths, we leave the graph unchanged and analyze properties of the solution on the graph.

It was shown that the problem is FPT for Treewidth but whether it allows polynomial kernel was not investigated. The main result shows that a polynomial kernel is impossible (under standard assumptions) for Fractioning Number (a.k.a. Vertex Integrity) and that a polynomial kernel can be achieved for Modulator to Constant Components and Feedback Edge Set. There are also several other results for some settings including negative one for Modulator to Disjoin Cycles for Subset TSP and positive ones for Subset TSP and WRP for Modulator to Constant Paths and Vertex Cover Number, respectively. See the poster below for a graphical overview.

The positive results on Vertex Cover use the notion of natural behavior – the cheapest way to connect a vertex outside of the vertex cover. Connecting all vertices in such a way may create an unconnected solution so we evaluate how costly is to change each behavior to the desired one (we try all combinations). It turns out that the number of behavior that use more than $2$ edges is small. As for each desired outcome we can keep only a limited number of natural behaviors (the ones that are cheapest to change to the desired one) we bound the total number of vertices that may not use their natural behavior. The ones that use natural behavior is solved implicitly and the rest is small – so we either get a NO-instance straight away or we get a kernel.

For an overview of the problem see the poster I made for the DIMEA Days 2022 below.