{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:37:12Z","timestamp":1787341032684,"version":"build-2736575974"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100011102","name":"European Union Seventh Framework Programme","doi-asserted-by":"crossref","award":["FP\/2007-2013"],"award-info":[{"award-number":["FP\/2007-2013"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["NK105645"],"award-info":[{"award-number":["NK105645"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["UMO-2013\/09\/B\/ST6\/03136"],"award-info":[{"award-number":["UMO-2013\/09\/B\/ST6\/03136"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"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\/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,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We prove the following theorem. Given a planar graph [Formula: see text] and an integer [Formula: see text], it is possible in polynomial time to randomly sample a subset [Formula: see text] of vertices of [Formula: see text] with the following properties: [Formula: see text] induces a subgraph of [Formula: see text] of treewidth [Formula: see text], and for every connected subgraph [Formula: see text] of [Formula: see text] on at most [Formula: see text] vertices, the probability that [Formula: see text] covers the whole vertex set of [Formula: see text] is at least [Formula: see text], where [Formula: see text] is the number of vertices of [Formula: see text]. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound [Formula: see text]. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed [Formula: see text]-Path, Weighted [Formula: see text]-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.<\/jats:p>","DOI":"10.1137\/19m1262504","type":"journal-article","created":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T15:16:08Z","timestamp":1671203768000},"page":"1866-1930","source":"Crossref","is-referenced-by-count":6,"title":["Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering"],"prefix":"10.1137","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":true,"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, N-5020 Bergen, Norway."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106-5110 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarland Informatics Campus, 66123 Saarbr\u00fccken, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":true,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, 02-097 Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, 02-097 Warsaw, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai 600 113, India, and Department of Informatics, University of Bergen, N-5020 Bergen, Norway."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,12,20]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0116-5"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191198768"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"Y. Bartal , On approximating arbitrary metrices by tree metrics, in Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, STOC 1998, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"ref6","unstructured":"H. L. Bodlaender , \nJ. Nederlof , and \nT. C. van der Zanden , Subexponential time algorithms for embedding H-minor free graphs, in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, LIPIcs Int. Proc. Inform. 55, Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2016, 9."},{"key":"ref7","first-page":"36","volume":"3","author":"Borradaile G.","year":"2014","journal-title":"Dagstuhl Rep."},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"M. Charikar , \nC. Chekuri , \nA. Goel , \nS. Guha , and \nS. A. Plotkin , Approximating a finite metric by a small number of tree metrics, in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1998, 1998, pp. 379\u2013388, https:\/\/doi.org\/10.1109\/SFCS.1998.743488.","DOI":"10.1109\/SFCS.1998.743488"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.04.016"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"ref13","first-page":"51","volume":"3","author":"Demaine E. D.","year":"2013","journal-title":"Dagstuhl Rep."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"ref16","unstructured":"E. D. Demaine  and \nM. T. Hajiaghayi , Equivalence of local treewidth and linear local treewidth and its algorithmic applications, in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, SIAM, 2004, pp. 840\u2013849."},{"key":"ref17","unstructured":"F. Dorn , Planar subgraph Isomorphism revisited, in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, LIPIcs Int. Proc. Inform. 5, Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2010, pp. 263\u2013274."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.11.006"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.02.004"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00014"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.003"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"F. V. Fomin , \nD. Lokshtanov , and \nS. Saurabh , Bidimensionality and geometric graphs, in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, SIAM, 2012, pp. 1563\u20131575.","DOI":"10.1137\/1.9781611973099.124"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"P. N. Klein  and \nD. Marx , A subexponential parameterized algorithm for subset TSP on planar graphs, in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, SIAM, 2014, pp. 1812\u20131830.","DOI":"10.1137\/1.9781611973402.131"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"D. Marx , \nM. Pilipczuk , and \nM. Pilipczuk , On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs, in Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018, 2018, pp. 474\u2013484.","DOI":"10.1109\/FOCS.2018.00052"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/19M1304088"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90687-B"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"M. Naor , \nL. J. Schulman , and \nA. Srinivasan , Splitters and near-optimal derandomization, in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1995, 1995, pp. 182\u2013191.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"ref35","unstructured":"M. Pilipczuk , \nM. Pilipczuk , \nP. Sankowski , and \nE. J. van Leeuwen , Subexponential-time parameterized algorithm for Steiner tree on planar graphs, in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, LIPIcs Int. Proc. Inform. 20, Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2013, pp. 353\u2013364."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.02.002"},{"key":"ref40","unstructured":"S. Tazari , Algorithmic Graph Minor Theory: Approximation, Parameterized Complexity, and Practical Aspects, Ph.D. thesis, Humboldt University of Berlin, 2010."},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.014"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1262504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:02:35Z","timestamp":1787338955000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1262504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,20]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1137\/19M1262504"],"URL":"https:\/\/doi.org\/10.1137\/19m1262504","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,20]]}}}