El problema del vendedor viajero en grafos cúbicos

Abstract

Dada una colección de ciudades y el costo de viajar entre cualquier par de ella, el problema del vendedor viajero, que denotaremos como TSP (traveling salesman problem en inglés), consiste en encontrar el tour menos costoso que visita todas las ciudades al menos una vez retornando al punto inicial. En su forma métrica este problema es NP-duro, y por lo tanto no existe un algoritmo en tiempo polinomial que lo resuelva, salvo que P=NP. Para el caso métrico, Christofides diseñó en el año 1976 un 3/2-algoritmo de aproximación, el cual despertó una gran curiosidad con respecto a la aproximabilidad del problema. Sin embargo, y pese a los grandes esfuerzos efectuados en investigación, el algoritmo de Christofides es el de mejor garantía hasta el día de hoy. Recientemente han habido varios mejoras importantes con respecto a la aproximabilidad en casos especiales de TSP métrico. En el año 2011 Oveis Gharan et al. diseñaron un (3/2-ε)-algoritmo de aproximación para el caso graph-TSP, donde la distancia métrica entre cada par de ciudades está dada por el menor número de arcos necesarios para conectarlas por un camino dentro de un grafo sin pesos. En el mismo año Mömke y Svensson mejoran el resultado a 1.461, mientras Mucha en el 2012 mejora la garantía del algoritmo a 13/9. En el caso de que el grafo es cúbico de n vértices y 2-conexo, el algoritmo de Mömke y Svensson entrega un tour de largo menor a (4/3)n, resultado obtenido también por Boyd et al. en el año 2011. En este trabajo estudiamos el problema graph-TSP en distintas variantes de grafos cúbicos. Primero estudiamos el caso en que el grafo es planar, cúbico, bipartito y 3-conexo, el cual es un caso interesante desde el punto de vista de teoría de grafos ya que, según la conjetura de Barnette de hace más de 40 años estos grafos serían Hamiltonianos. En esta clase de grafos, conocidos como grafos de Barnette, mostramos que en un grafo de n vértices existe un tour de largo a lo más (4/3-1/18)n. Luego relajamos las condiciones sobre el grafo, quitando la hipótesis de planaridad e imponiendo que sea cúbico, bipartito y 2-conexo, caso en el cual mostramos que existe un tour de largo a lo más (4/3-1/108)n. Finalmente, estudiamos el caso en que el grafo es solamente cúbico y 2-conexo. En este caso nos basamos en las técnicas de Boyd et al. para mostrar que existe un tour de largo a lo más (4/3-1/61236)n. En cada caso mostramos que el tour se puede encontrar en tiempo polinomial, y como n es naturalmente una cota inferior del valor de graph-TSP, cada uno de los resultados obtenidos se traduce en un algoritmo de aproximación. Además, como n es una cota inferior de la relajación de Held & Karp, que es una conocida formulación para TSP como programa lineal, obtenemos como consecuencia que el gap de integralidad de TSP con respecto a esta relajación es acotado superiormente por (4/3-1/18) para el caso de Barnette, (4/3-1/108) para el caso cúbico, bipartito y 2-conexo, y (4/3-1/61236) para el caso cúbico y 2-conexo.