{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:20Z","timestamp":1787340440225,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["UMO-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["UMO-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>There are numerous examples of the so-called \u201csquare root phenomenon\u201d in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter $k$, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in $\\mathcal{O}(\\sqrt{k})$ instead of $\\mathcal{O}(k)$ (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals $T$ by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number $k=|T|$ of terminals is regarded as the parameter. We show that Subset TSP can be solved in time $2^{\\mathcal{O}(\\sqrt{k}\\log k)}\\cdot n^{\\mathcal{O}(1)}$ even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [ SODA 2014, SIAM, Philadelphia, 2014, pp. 1812--1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights.<\/jats:p>","DOI":"10.1137\/19m1304088","type":"journal-article","created":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T12:39:59Z","timestamp":1649335199000},"page":"254-289","source":"Crossref","is-referenced-by-count":1,"title":["A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs"],"prefix":"10.1137","volume":"51","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":true,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,4,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22109"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897549"},{"key":"atypb3","first-page":"639","author":"Bateni M. H.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"atypb5","first-page":"9","author":"Bodlaender H. L.","year":"2016","journal-title":"Germany"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2831235"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"atypb8","first-page":"1782","author":"Chitnis R. H.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, Cham, Switzerland, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/130947076"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9296-1"},{"key":"atypb13","first-page":"626","author":"Eisenstat D.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb14","first-page":"617","author":"Eisenstat D.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering\n                      , in FOCS 2016, IEEE Computer Society, Los Alamitos, CA, 2016, pp. 515-524.","DOI":"10.1109\/FOCS.2016.62"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20121"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746564"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367070"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/060649562"},{"key":"atypb20","first-page":"569","author":"Klein P. N.","year":"2012","journal-title":"Berlin"},{"key":"atypb21","first-page":"1812","author":"Klein P. N.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb22","first-page":"554","volume":"9294","author":"Klein P. N.","year":"2015","journal-title":"Lecture Notes in Comput. Sci."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104834"},{"key":"atypb24","first-page":"424","author":"Lokshtanov D.","year":"2012","journal-title":"Germany"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"atypb26","first-page":"865","author":"Marx D.","year":"2015","journal-title":"Berlin"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"D. Marx, M. Pilipczuk, and M. Pilipczuk,\n                      On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs\n                      , in 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, IEEE Computer Society, Los Alamitos, CA, 2018, pp. 474-484.","DOI":"10.1109\/FOCS.2018.00052"},{"key":"atypb29","first-page":"353","author":"Pilipczuk M.","year":"2013","journal-title":"Germany"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"M. Pilipczuk, M. Pilipczuk, P. Sankowski, and E. J. van Leeuwen,\n                      Network sparsification for Steiner problems on planar and bounded-genus graphs\n                      , in FOCS 2014, IEEE Computer Society, Los Alamitos, CA, 2014, pp. 276-285.","DOI":"10.1109\/FOCS.2014.37"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1304088","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:35:12Z","timestamp":1787337312000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1304088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1137\/19M1304088"],"URL":"https:\/\/doi.org\/10.1137\/19m1304088","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}