Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems

Given the minimum Hamiltonian path (or traveling salesman tour) H⁰ in an undirected weighted graph, the sensitivity analysis problem consists in finding by how much we can perturb each edge weight individually without changing the optimality of H⁰.

The maximum increment and decrement of the edge weight that preserve the optimality of H⁰ is called edge tolerance with respect to the solution H⁰. A method of computing lower bounds of edge tolerances based on solving the sensitivity analysis problem for appropriate relaxations of the minimum Hamiltonian path and traveling salesman problems is presented.