Document Open Access Logo

On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations

Authors Václav Blažej , Pratibha Choudhary , Dušan Knop , Šimon Schierreich , Ondřej Suchý , Tomáš Valla

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.22.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Václav Blažej
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Pratibha Choudhary
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Dušan Knop
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Šimon Schierreich
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Ondřej Suchý
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Tomáš Valla
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic

Funding

The authors acknowledge the support of the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16_019/0000765 "Research Center for Informatics". This work was additionally supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS20/208/OHK3/3T/18.

Cite AsGet BibTex

Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla. On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.22

Abstract

For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • Traveling Salesperson
  • Subset TSP
  • Waypoint Routing
  • Kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Saeed Akhoondian Amiri, Klaus-Tycho Foerster, and Stefan Schmid. Walking through waypoints. Algorithmica, 82(7):1784-1812, 2020. URL: https://doi.org/10.1007/s00453-020-00672-z.
  2. David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2011. URL: https://doi.org/10.1515/9781400841103.
  3. Sanjeev Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96, pages 2-11. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/SFCS.1996.548458.
  4. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753-782, September 1998. URL: https://doi.org/10.1145/290179.290180.
  5. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1):61-63, January 1962. URL: https://doi.org/10.1145/321105.321111.
  6. Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard Woeginger. Fine-grained complexity analysis of two classic TSP variants. ACM Transactions on Algorithms, 17(1), December 2021. URL: https://doi.org/10.1145/3414845.
  7. Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik. Fine-grained complexity of k-OPT in bounded-degree graphs for solving TSP. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, Proceedings of the 27th Annual European Symposium on Algorithms, ESA '19, volume 144 of Leibniz International Proceedings in Informatics, pages 23:1-23:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.23.
  8. Sylvia C. Boyd and Robert Carr. Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization, 8(4):525-539, 2011. URL: https://doi.org/10.1016/j.disopt.2011.05.002.
  9. Leizhen Cai. Parameterized complexity of vertex colouring. Discrete Applied Mathematics, 127(3):415-429, 2003. URL: https://doi.org/10.1016/S0166-218X(02)00242-1.
  10. Robert D. Carr, Santosh S. Vempala, and Jacques Mandler. Towards a 4/3 approximation for the asymmetric traveling salesman problem. In David B. Shmoys, editor, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, pages 116-125. ACM/SIAM, 2000. Google Scholar
  11. Timothy M. Chan and R. Ryan Williams. Deterministic APSP, Orthogonal Vectors, and more: Quickly derandomizing Razborov-Smolensky. ACM Transactions on Algorithms, 17(1):2:1-2:14, 2021. URL: https://doi.org/10.1145/3402926.
  12. Miroslav Chlebík and Janka Chlebíková. Approximation hardness of travelling salesman via weighted amplifiers. In Ding-Zhu Du, Zhenhua Duan, and Cong Tian, editors, Proceedings of the 25th International Conference on Computing and Combinatorics, COCOON '19, volume 11653 of Lecture Notes in Computer Science, pages 115-127, Cham, 2019. Springer. URL: https://doi.org/10.1007/978-3-030-26176-4_10.
  13. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon University Pittsburgh, Management Sciences Research Group, 1976. Google Scholar
  14. Gérard Cornuéjols, Jean Fonlupt, and Denis Naddef. The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming, 33(1):1-27, 1985. URL: https://doi.org/10.1007/BF01582008.
  15. G. A. Croes. A method for solving traveling-salesman problems. Operations Research, 6(6):791-812, December 1958. URL: https://doi.org/10.1287/opre.6.6.791.
  16. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, Cham, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  17. Marek Cygan, Łukasz Kowalik, and Arkadiusz Socała. Improving TSP tours using dynamic programming over tree decompositions. ACM Transactions on Algorithms, 15(4), October 2019. URL: https://doi.org/10.1145/3341730.
  18. Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5th edition, 2017. URL: https://doi.org/10.1007/978-3-662-53622-3.
  19. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Information and Computation, 209(2):143-153, 2011. URL: https://doi.org/10.1016/j.ic.2010.11.026.
  20. Jiří Fiala, Petr A. Golovach, and Jan Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theoretical Computer Science, 412(23):2513-2523, 2011. URL: https://doi.org/10.1016/j.tcs.2010.10.043.
  21. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM Journal on Computing, 39(5):1941-1956, 2010. URL: https://doi.org/10.1137/080742270.
  22. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. URL: https://doi.org/10.1007/BF02579200.
  23. David Gamarnik, Moshe Lewenstein, and Maxim Sviridenko. An improved upper bound for the TSP in cubic 3-edge-connected graphs. Operations Research Letters, 33(5):467-474, 2005. URL: https://doi.org/10.1016/j.orl.2004.09.005.
  24. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  25. Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In Rafail Ostrovsky, editor, Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science, FOCS '11, pages 550-559. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.80.
  26. Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP. Mathematical Programming, 69:335-349, 1995. URL: https://doi.org/10.1007/BF01585563.
  27. Michelangelo Grigni, Elias Koutsoupias, and Christos H. Papadimitriou. An approximation scheme for planar graph TSP. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS '95, pages 640-645. IEEE Computer Society, 1995. URL: https://doi.org/10.1109/SFCS.1995.492665.
  28. Jiong Guo, Sepp Hartung, Rolf Niedermeier, and Ondřej Suchý. The parameterized complexity of local search for TSP, more refined. Algorithmica, 67(1):89-110, 2013. URL: https://doi.org/10.1007/s00453-012-9685-8.
  29. Gregory Gutin and Abraham P. Punnen, editors. The traveling salesman problem and its variations. Combinatorial Optimization. Springer, Boston, MA, 2007. URL: https://doi.org/10.1007/b101971.
  30. Arash Haddadan and Alantha Newman. Towards improving Christofides algorithm for half-integer TSP. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, Proceedings of the 27th Annual European Symposium on Algorithms, ESA '19, volume 144 of Leibniz International Proceedings in Informatics, pages 56:1-56:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.56.
  31. Michael Held and Richard M. Karp. The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1:6-25, 1971. URL: https://doi.org/10.1007/BF01584070.
  32. Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (Turing) kernelization. Algorithmica, 71(3):702-730, 2015. URL: https://doi.org/10.1007/s00453-014-9910-8.
  33. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, March 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  34. Bart M. P. Jansen and Stefan Kratsch. Data reduction for graph coloring problems. Information and Computation, 231:70-88, 2013. URL: https://doi.org/10.1016/j.ic.2013.08.005.
  35. David S. Johnson and Lyle A. McGeoch. Experimental analysis of heuristics for the STSP. In Gregory Gutin and Abraham P. Punnen, editors, The Traveling Salesman Problem and Its Variations, pages 369-443. Springer, Boston, MA, 2007. URL: https://doi.org/10.1007/0-306-48213-4_9.
  36. David S. Johnson and Lyle A. McGeoch. The traveling salesman problem: a case study. In Emile Aarts and Jan Karel Lenstra, editors, Local Search in Combinatorial Optimization, pages 215-310. Princeton University Press, 2018. URL: https://doi.org/10.1515/9780691187563-011.
  37. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. An improved approximation algorithm for TSP in the half integral case. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC '20, pages 28-39. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384273.
  38. Philip N. Klein. A linear-time approximation scheme for planar weighted TSP. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS '05, pages 647-657. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.7.
  39. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for subset TSP on planar graphs. In Chandra Chekuri, editor, Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 1812-1830. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.131.
  40. Giuseppe Lancia and Marcello Dalpasso. Algorithmic strategies for a fast exploration of the TSP 4-opt neighborhood. In Massimo Paolucci, Anna Sciomachen, and Pierpaolo Uberti, editors, Advances in Optimization and Decision Science for Society, Services and Enterprises, volume 3 of AIRO Springer Series, pages 457-470. Springer, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-34960-8_40.
  41. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Brief announcement: Treewidth modulator: Emergency exit for DFVS. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP '18, volume 107 of Leibniz International Proceedings in Informatics, pages 110:1-110:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.110.
  42. Diptapriyo Majumdar, Venkatesh Raman, and Saket Saurabh. Polynomial kernels for vertex cover parameterized by small degree modulators. Theory of Computing Systems, 62(8):1910-1951, 2018. URL: https://doi.org/10.1007/s00224-018-9858-1.
  43. Isja Mannens, Jesper Nederlof, Céline M. F. Swennenhuis, and Krisztina Szilágyi. On the parameterized complexity of the connected flow and many visits TSP problem. In Łukasz Kowalik, Michał Pilipczuk, and Pawel Rzazewski, editors, Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG '21, volume 12911 of Lecture Notes in Computer Science, pages 52-79. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-86838-3_5.
  44. Isja Mannens, Jesper Nederlof, Céline M. F. Swennenhuis, and Krisztina Szilágyi. On the parameterized complexity of the connected flow and many visits TSP problem. CoRR, abs/2106.11689, 2021. URL: http://arxiv.org/abs/2106.11689.
  45. Dániel Marx. Searching the k-change neighborhood for TSP is W[1]-hard. Operations Research Letters, 36(1):31-36, 2008. URL: https://doi.org/10.1016/j.orl.2007.02.008.
  46. Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk. On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. In Mikkel Thorup, editor, Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS '18, pages 474-484. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00052.
  47. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM Journal on Computing, 28(4):1298-1309, March 1999. URL: https://doi.org/10.1137/S0097539796309764.
  48. Tobias Mömke and Ola Svensson. Approximating graphic TSP by matchings. In Rafail Ostrovsky, editor, Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science, FOCS '11, pages 560-569. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.56.
  49. Marcin Mucha. 13/9-approximation for graphic TSP. In Christoph Dürr and Thomas Wilke, editors, Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, STACS '12, volume 14 of Leibniz International Proceedings in Informatics, pages 30-41. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.30.
  50. Christos H. Papadimitriou and Mihalis Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1-11, February 1993. URL: https://www.jstor.org/stable/3690150.
  51. Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM, 23(3):555-565, July 1976. URL: https://doi.org/10.1145/321958.321975.
  52. Šimon Schierreich and Ondřej Suchý. Waypoint routing on bounded treewidth graphs. Information Processing Letters, 173:106165, 2022. URL: https://doi.org/10.1016/j.ipl.2021.106165.
  53. András Sebö and Jens Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597-629, 2014. URL: https://doi.org/10.1007/s00493-014-2960-3.
  54. David B. Shmoys and David P. Williamson. Analyzing the Held-Karp TSP bound: A monotonicity property with application. Information Processing Letters, 35(6):281-285, 1990. URL: https://doi.org/10.1016/0020-0190(90)90028-V.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact