Parameterized Traveling Salesman Problem: Beating the Average

In the traveling salesman problem (TSP), we are given a complete graph Kn together
with an integer weighting w on the edges of Kn, and we are asked to find a Hamilton cycle of
Kn of minimum weight. Let h(w) denote the average weight of a Hamilton cycle of Kn for the
weighting w. Vizing in 1973 asked whether there is a polynomial-time algorithm which always
finds a Hamilton cycle of weight at most h(w). He answered this question in the affirmative and
subsequently Rublineckii, also in 1973, and others described several other TSP heuristics satisfying
this property. In this paper, we prove a considerable generalization of Vizing’s result: for each fixed
k, we give an algorithm that decides whether, for any input edge weighting w of Kn, there is a
Hamilton cycle of Kn of weight at most h(w) − k (and constructs such a cycle if it exists). For k
fixed, the running time of the algorithm is polynomial in n, where the degree of the polynomial does
not depend on k (i.e., the generalized Vizing problem is fixed-parameter tractable with respect to
the parameter k).