Abstract
We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) “Edge Exchange” and “Max-Shift”. We perform studies with respect to the distance measures “Swap” and “r-Swap”, “Reversal” and “r-Reversal”, and “Edit”, achieving both fixed-parameter tractability and W[1]-hardness results. In particular, from the parameterized reduction showing W[1]-hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs.
Similar content being viewed by others
References
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)
Balas, E.: New classes of efficiently solvable generalized traveling salesman problems. Ann. Oper. Res. 86, 529–558 (1999)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)
Bodlaender, H.L.: Kernelization: new upper and lower bound techniques. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC ’09). Lecture Notes in Computer Science, vol. 5917, pp. 17–37. Springer, Berlin (2009)
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)
Caprara, A.: Sorting by reversals is difficult. In: Proceedings of the 1st Conference on Research in Computational Molecular Biology (RECOMB ’97), pp. 75–83. ACM, New York (1997)
Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216–231 (2005)
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie Mellon University Pittsburgh , Management Sciences Research Group (1976)
Deineko, V.G., Woeginger, G.J.: A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math. Program. 87(3), 519–542 (2000)
Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58, 790–810 (2010)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
Fellows, M.R.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Proceedings of the 20th International Workshop on Combinatorial Algorithms (IWOCA ’09). Lecture Notes in Computer Science, vol. 5874, pp. 2–10. Springer, Berlin (2009)
Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53–61 (2009)
Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Villanger, Y.: Local search: is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707–719 (2012)
Fertin, G., Labarre, A., Rusu, I., Tannier, É., Vialette, S.: Combinatorics of Genome Rearrangements. MIT Press, Cambridge (2009)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Fomin, F., Lokshtanov, D., Raman, V., Saurabh, S.: Fast local search algorithm for weighted feedback arc set in tournaments. In: Proceedings of the 24th Conference on Artificial Intelligence (AAAI ’10), pp. 65–70 (2010)
Garey, M., Johnson, D., Tarjan, R.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704–714 (1976)
Gaspers, S., Kim, E.J., Ordyniak, S., Saurabh, S., Szeider, S.: Don’t be strict in local search. In: Proceedings of the 26th Conference on Artificial Intelligence (AAAI ’12), pp. 486–492 (2012)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)
Gutin, G., Punnen, A.: The Traveling Salesman Problem and Its Variations. Kluwer Academic, Norwell (2002)
Gutin, G., Yeo, A., Zverovitch, A.: Exponential neighborhoods and domination analysis for the TSP. In: The Traveling Salesman Problem and Its Variations, pp. 223–256. Kluwer Academic, Norwell (2002). Chapter 1
Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. In: Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC ’10). Lecture Notes in Computer Science, vol. 6108, pp. 258–270. Springer, Berlin (2010)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196–210 (1962)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)
Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case study in local optimization. In: Local Search in Combinatorial Optimization, pp. 215–310 (1997)
Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: The Traveling Salesman Problem and Its Variations, pp. 369–443. Kluwer Academic, Norwell (2004)
Krokhin, A., Marx, D.: On the hardness of losing weight. ACM Trans. Algorithms 8(2), 19:1–19:18 (2012)
Lawler, E., Lenstra, J., Kan, A., Shmoys, D.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, vol. 3. Wiley, New York (1985)
Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. Eur. Assoc. Theor. Comput. Sci. 84, 41–71 (2011)
Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization–preprocessing with a guarantee. In: The Multivariate Algorithmic Revolution and Beyond–Essays Dedicated to Michael R. Fellows. Lecture Notes in Computer Science, vol. 7370, pp. 130–161. Springer, Berlin (2012)
Marx, D.: Searching the k-change neighborhood for TSP is W[1]-hard. Oper. Res. Lett. 36(1), 31–36 (2008)
Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85–112 (2010)
Marx, D., Schlotter, I.: Stable assignment with couples: parameterized complexity and local search. Discrete Optim. 8(1), 25–40 (2011)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)
Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS ’10). LIPIcs, vol. 5, pp. 17–32 (2010). Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik
Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B 41, 92–114 (1986)
Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52(2), 153–190 (1991)
Szeider, S.: The parameterized complexity of k-flip local search for SAT and MAX SAT. Discrete Optim. 8(1), 139–145 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
The first and the fourth author were supported by the DFG Cluster of Excellence on Multimodal Computing and Interaction (MMCI) and the DFG project DARE (GU 1023/1-2). Most of the work of Ondřej Suchý was done while he was with MMCI Saarbrücken.
An extended abstract of this paper appeared in Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC’11), Yokohama, Japan, Dec. 2011, volume 7074 of LNCS, pages 614–623, Springer, 2011. An important difference compared to the conference version is that we significantly improved the running time lower bounds.
Rights and permissions
About this article
Cite this article
Guo, J., Hartung, S., Niedermeier, R. et al. The Parameterized Complexity of Local Search for TSP, More Refined. Algorithmica 67, 89–110 (2013). https://doi.org/10.1007/s00453-012-9685-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-012-9685-8