We consider the Asymmetric Traveling Salesman Problem (ATSP) and use the definition of neighborhood by Deineko and Woeginger (see Math. Programming 87 (2000) 519-542). Let $\mu(n)$ be the maximum cardinality of polynomial time searchable neighborhood for the ATSP on $n$ vertices. Deineko and Woeginger conjectured that $\mu (n)< \beta (n-1)!$ for any constant $\beta >0$ provided P$\neq$NP. We prove that $\mu(n) < \beta (n-k)!$ for any fixed integer $k\ge 1$ and constant $\beta >0$ provided NP$\not\subseteq$P/poly, which (like P$\neq$NP) is believed to be true. We also give upper bounds for the size of an ATSP neighborhood depending on its search time.
Citation
Technical Report TR-01-01, Dept of Computer Science, Royal Holloway University of London, UK, April 2001