Short Tours through Large Linear Forests
- Uriel Feige ,
- R. Ravi ,
- Mohit Singh
In Proceedings of 17th Conference on Integer Programming and Combinatorial Optimization (IPCO 2014) |
A tour in a graph is a connected walk that visits every vertex at least once, and returns to the starting vertex. Vishnoi [18] proved that every connected d-regular graph with n vertices has a tour of length at most (1 + o(1))n, where the o(1) term (slowly) tends to 0 as d grows. His proof is based on van-der-Warden’s conjecture (proved independently by Egorychev [8] and by Falikman [9]) regarding the permanent of doubly stochastic matrices. We provide an exponential improvement in the rate of decrease of the o(1) term (thus increasing the range of d for which the upper bound on the tour length is nontrivial). Our proof does not use the van-der-Warden conjecture, and instead is related to the linear arboricity conjecture of Akiyama, Exoo and Harary [1], or alternatively, to a conjecture of Magnant and Martin [12] regarding the path cover number of regular graphs. More generally, for arbitrary connected graphs, our techniques provide an upper bound on the minimum tour length, expressed as a function of their maximum, average, and minimum degrees. Our bound is best possible up to a term that tends to 0 as the minimum degree grows.