{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T08:03:03Z","timestamp":1784534583880,"version":"3.55.0"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["218001"],"award-info":[{"award-number":["218001"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. In the problem [Formula: see text]-Tour defined within this model, the objective is to find a shortest tour that comes within a distance of [Formula: see text] of every point on every edge. This problem was introduced in the predecessor to this article and shown to be essentially equivalent to the Chinese Postman problem for [Formula: see text], to the graphic Travel Salesman Problem (TSP) for [Formula: see text], and close to first vertex cover and then dominating set for even larger [Formula: see text]. Moreover, approximation algorithms for multiple parameter ranges were provided. In this article, we provide complementing inapproximability bounds and examine the fixed-parameter tractability of the problem. On the one hand, we show the following: (1) For every fixed [Formula: see text], the problem [Formula: see text]-Tour is APX-hard, while for every fixed [Formula: see text], the problem has no polynomial-time [Formula: see text]-approximation unless [Formula: see text]. Our techniques also yield the new result that TSP remains APX-hard on cubic (and even cubic bipartite) graphs. (2) For every fixed [Formula: see text], the problem [Formula: see text]-Tour is fixed-parameter tractable (FPT) when parameterized by the length of a shortest tour, while it is W[2]-hard for every fixed [Formula: see text] and para-NP-hard for [Formula: see text] being part of the input. On the other hand, if [Formula: see text] is considered to be part of the input, then an interesting nontrivial phenomenon occurs when [Formula: see text] is a constant fraction of the number of vertices: (3) If [Formula: see text] is part of the input, then the problem can be solved in time [Formula: see text], where [Formula: see text]; however, assuming the exponential-time hypothesis (ETH), there is no algorithm that solves the problem and runs in time [Formula: see text].<\/jats:p>","DOI":"10.1137\/25m1736402","type":"journal-article","created":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T07:15:26Z","timestamp":1784531726000},"page":"1066-1106","source":"Crossref","is-referenced-by-count":0,"title":["From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity"],"prefix":"10.1137","volume":"40","author":[{"given":"Fabian","family":"Frei","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Artifical Intelligence and Computer Science Laboratory, Cambridge, MA 02139 USA."},{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ahmed","family":"Ghazy","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security and Saarland University, Saarbr\u00fccken."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim A.","family":"Hartmann","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"H\u00f6rsch","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,20]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62592-5_80"},{"key":"ref2","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2022","edition":"4"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.8.4.333"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_17"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.12.001"},{"key":"ref7","unstructured":"F. Frei, A. Ghazy, T. A. Hartmann, F. H\u00f6rsch, and D. Marx, From Chinese Postman to Salesman and Beyond: Shortest Tour \\(\\delta\\)-Covering All Points on All Edges, CoRR, abs\/2410.10613, 2024, https:\/\/doi.org\/10.48550\/arXiv.2410.10613."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-81396-2_5"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01646-x"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"M. Karpinski, Towards better inapproximability bounds for TSP: A challenge of global dependencies, in Proceedings of the 20th International Symposium on Fundamentals of Computation Theory (FCT 2015), Lecture Notes in Computer Science 9210, A. Kosowski and I. Walukiewicz, eds. Springer, 2015, pp. 3\u201311, https:\/\/doi.org\/10.1007\/978-3-319-22177-9_1.","DOI":"10.1007\/978-3-319-22177-9_1"},{"key":"ref11","unstructured":"M. Karpinski and R. Schmied, Improved inapproximability results for the shortest superstring and the bounded metric TSP, https:\/\/theory.cs.uni-bonn.de\/ftp\/reports\/cs-reports\/2013\/85339-CS.pdf, Accessed: 2024-04-01."},{"key":"ref12","unstructured":"M. Karpinski and R. Schmied, On Approximation Lower Bounds for TSP with Bounded Metrics, CoRR, abs\/1201.5821, 2012, http:\/\/arxiv.org\/abs\/1201.5821."},{"key":"ref13","unstructured":"M. Karpinski and R. Schmied, Improved inapproximability results for the shortest superstring and related problems, in Nineteenth Computing: The Australasian Theory Symposium, CATS 2013, Adelaide, Australia, February 2013, CRPIT 141, A. Wirth, ed. Australian Computer Society, 2013, pp. 27\u201336, http:\/\/crpit.scem.westernsydney.edu.au\/abstracts\/CRPITV141Karpinski.html."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/2014062"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/3325116"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"C. S. Karthik, D. Marx, M. Pilipczuk, and U. S. Souza, Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof, in Proceedings of 2024 Symposium on Simplicity in Algorithms (SOSA), 2024, pp. 383\u2013395, https:\/\/doi.org\/10.1137\/1.9781611977936.35.","DOI":"10.1137\/1.9781611977936.35"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.27"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9148-9"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"ref20","volume-title":"Combinatorial Optimization \u2013 Polyhedra and Efficiency","author":"Schrijver A.","year":"2003"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.11.3.243"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T07:15:28Z","timestamp":1784531728000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1736402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,20]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1137\/25M1736402"],"URL":"https:\/\/doi.org\/10.1137\/25m1736402","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,20]]}}}