{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:44:34Z","timestamp":1787341474649,"version":"build-2736575974"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100012226","name":"European Research Council","doi-asserted-by":"publisher","award":["101039913"],"award-info":[{"award-number":["101039913"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"European Research Council","doi-asserted-by":"publisher","award":["948057"],"award-info":[{"award-number":["948057"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"European Research Council","doi-asserted-by":"publisher","award":["715744"],"award-info":[{"award-number":["715744"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States\u2013Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018302"],"award-info":[{"award-number":["2018302"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In the disjoint paths problem, the input is an undirected graph [Formula: see text] on [Formula: see text] vertices and a set of [Formula: see text] vertex pairs, [Formula: see text], and the task is to find [Formula: see text] pairwise vertex-disjoint paths such that the [Formula: see text]\u2019th path connects [Formula: see text] to [Formula: see text]. In this paper, we give a parameterized algorithm with running time [Formula: see text] for planar disjoint paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage\/treewidth reduction theorem for planar graphs by Adler et\u00a0al. [ J. Combin. Theory Ser. B, 122 (2017), pp. 815\u2013843], the algebraic cohomology based technique of Schrijver [ SIAM J. Comput., 23 (1994), pp. 780\u2013788], and one of the key combinatorial insights developed by Cygan et\u00a0al. [ Proceedings of the 2013 IEEE 54 th Annual Symposium on Foundations of Computer Science, 2013, pp. 197\u2013206] in their algorithm for disjoint paths on directed planar graphs. To the best of our knowledge, our algorithm is the first parameterized algorithm to exploit the fact that the treewidth of the input graph is small, and it does so in a way that is completely different from the use of dynamic programming.<\/jats:p>","DOI":"10.1137\/20m1355902","type":"journal-article","created":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T04:18:46Z","timestamp":1741925926000},"page":"321-418","source":"Crossref","is-referenced-by-count":1,"title":["An Exponential Time Parameterized Algorithm for Planar Disjoint Paths"],"prefix":"10.1137","volume":"54","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Siruseri, Tamil Nadu 603103, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw 02-097, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, Tamil Nadu 600113, India; University of Bergen, 5007 Bergen, Norway; and IRL 2000 ReLaX, Chennai Mathematical Institute, Siruseri, Tamil Nadu 603103, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheba, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,3,14]]},"reference":[{"key":"ref1","unstructured":"I. Adler, Undirected k disjoint paths, in List of Open Problems, 6th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2013), Santorini Island, 2013, p. 2, https:\/\/www.cs.upc.edu\/~sedthilk\/grow\/Open_Problems_GROW_2013.pdf."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.10.001"},{"key":"ref3","unstructured":"I. Adler and P. K. Krause, A Lower Bound for the Tree-Width of Planar Graphs with Vital Linkages, preprint, https:\/\/arxiv.org\/abs\/1011.2136."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.12.010"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/2820609"},{"key":"ref8","series-title":"LIPIcs 40","first-page":"187","volume-title":"Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques (APPROX\/RANDOM 2015)","author":"Chuzhoy J.","year":"2015"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, D. H. K. Kim, and S. Li, Improved approximation for node-disjoint paths in planar graphs, in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 2016, pp. 556\u2013569, https:\/\/doi.org\/10.1145\/2897518.2897538.","DOI":"10.1145\/2897518.2897538"},{"key":"ref10","first-page":"STOC17-189","volume":"5","author":"Chuzhoy J.","year":"2020","journal-title":"SIAM J. Comput."},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, D. H. K. Kim, and R. Nimavat, Almost polynomial hardness of node-disjoint paths in grids, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, ACM, 2018, pp. 1220\u20131233, https:\/\/doi.org\/10.1145\/3188745.3188772.","DOI":"10.1145\/3188745.3188772"},{"key":"ref12","unstructured":"J. Chuzhoy, D. H. K. Kim, and R. Nimavat, Improved approximation for node-disjoint paths in grids with sources on the boundary, in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, LIPIcs 107, 2018, pp. 38:1\u201338:14, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.38."},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad, \u00c9.C. de Verdi\u00e8re, P. N. Klein, C. Mathieu, and D. Meierfrankenfeld, Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 2016, pp. 584\u2013597, https:\/\/doi.org\/10.1145\/2897518.2897635.","DOI":"10.1145\/2897518.2897635"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00265"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"M. Cygan, D. Marx, M. Pilipczuk, and M. Pilipczuk, The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable, in Proceedings of the 2016 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), Berkeley, CA, 2013, pp. 197\u2013206, https:\/\/doi.org\/10.1109\/FOCS.2013.29.","DOI":"10.1109\/FOCS.2013.29"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"ref18","series-title":"Grad Texts in Math 173","volume-title":"Graph Theory","author":"Diestel R.","year":"2005","edition":"3"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/0405009"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering, in Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science(FOCS 2016), New Brunswick, NJ, 2016, pp. 515\u2013524.","DOI":"10.1109\/FOCS.2016.62"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/3154833"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"ref23","series-title":"Algorithms and Combinatorics 9","first-page":"49","volume-title":"Paths, Flows and VLSI-Layout","author":"Frank A.","year":"1990"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"M. Grohe, K. Kawarabayashi, and B. Reed, A simple algorithm for the graph minor decomposition\u2014logic meets structural graph theory, in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, LA, SIAM, 2013, pp. 414\u2013431, https:\/\/doi.org\/10.1137\/1.9781611973105.30.","DOI":"10.1137\/1.9781611973105.30"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"B. M. P. Jansen, D. Lokshtanov, and S. Saurabh, A near-optimal planarization algorithm, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR, 2014, pp. 1802\u20131811, https:\/\/doi.org\/10.1137\/1.9781611973402.130.","DOI":"10.1137\/1.9781611973402.130"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, the IBM Research Symposia Series, R. Miller, J. Thatcher, and J. Bohlinger, eds. Springer, 1972, pp. 85\u2013103, https:\/\/doi.org\/10.1007\/978-1-4684-2001-2.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.004"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and P. Wollan, A shorter proof of the graph minor algorithm: The unique linkage theorem, in Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, ACM, 2010, pp. 687\u2013694, https:\/\/doi.org\/10.1145\/1806689.1806784.","DOI":"10.1145\/1806689.1806784"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and P. Wollan, A simpler algorithm and shorter proof for the graph minor decomposition, in Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011), San Jose, CA, ACM, 2011, pp. 451\u2013458, https:\/\/doi.org\/10.1145\/1993636.1993697.","DOI":"10.1145\/1993636.1993697"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"P. N. Klein and D. Marx, A subexponential parameterized algorithm for subset TSP on planar graphs, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR, SIAM, 2014, pp. 1812\u20131830, https:\/\/doi.org\/10.1137\/1.9781611973402.131.","DOI":"10.1137\/1.9781611973402.131"},{"key":"ref33","first-page":"129","volume":"2","author":"Kramer M. R.","year":"1984","journal-title":"Adv. Comput. Res."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41422-0_20"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104834"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/1061425.1061430"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322048"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.12.007"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"ref44","volume":"3","author":"Scheffler P.","year":"1994","journal-title":"A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree-Width"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224061"},{"key":"ref46","series-title":"Algorithms Combin. 24","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1355902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:22:42Z","timestamp":1787340162000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1355902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,14]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1137\/20M1355902"],"URL":"https:\/\/doi.org\/10.1137\/20m1355902","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,14]]}}}