A quadratic-order problem kernel for the traveling salesman problem parameterized by the vertex cover number
share
The NP-hard graphical traveling salesman problem (GTSP) is to find a closed walk of total minimum weight that visits (at least once) each vertex in an undirected edge-weighted and not necessarily complete graph. Recently, Blažej et al. [ESA 2022] showed a problem kernel with O(τ^3) vertices for GTSP, where τ is the vertex cover number of the input graph. We present a problem kernel with only O(τ^2) vertices.
READ FULL TEXT