{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T05:44:59Z","timestamp":1790660699193,"version":"4.1.0"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":[". 024.002.003"],"award-info":[{"award-number":[". 024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We give an algorithmic and lower bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to intersection graphs of similarly-sized fat objects, yielding algorithms with running time $2^{O(n^{1-1\/d})}$ for any fixed dimension $d\\ge 2$ for many well-known graph problems, including Independent Set, $r$-Dominating Set for constant $r$, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms are representation-agnostic, i.e., they work on the graph itself and do not require the geometric representation. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into $d$-dimensional grids, and it allows us to derive matching $2^{\\Omega(n^{1-1\/d})}$ lower bounds under the exponential time hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.<\/jats:p>","DOI":"10.1137\/20m1320870","type":"journal-article","created":{"date-parts":[[2020,12,15]],"date-time":"2020-12-15T11:58:42Z","timestamp":1608033522000},"page":"1291-1331","source":"Crossref","is-referenced-by-count":17,"title":["A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs"],"prefix":"10.1137","volume":"49","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom C.","family":"van der Zanden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,12,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.001"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/120891241"},{"key":"atypb3","unstructured":"J. Baste and D. M. Thilikos,\n                      Contraction-Bidimensionality of Geometric Intersection Graphs\n                      , in 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), D. Lokshtanov and N. Nishimura, eds., Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, Vol. 89, 2018, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 5:1-5:13,https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.5."},{"key":"atypb4","first-page":"450","author":"Bergde Berg M.","year":"2018","journal-title":"NJ"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188854"},{"key":"atypb6","first-page":"31","author":"Bergde Berg M.","year":"2020","journal-title":"Switzerland"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.10.007"},{"key":"atypb8","first-page":"47","volume":"9","author":"Bir\u00f3 C.","year":"2018","journal-title":"J. Comput. Geom."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/130947374"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.008"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/0406014"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1026-5"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00014-X"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. 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":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.01.005"},{"key":"atypb20","unstructured":"F. V. Fomin, D. Lokshtanov, F. Panolan, S. Saurabh, and M. Zehavi,\n                      Finding, hitting and packing cycles in subexponential time on unit disk graphs\n                      , in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, LIPIcs Leibniz Int. Proc. Inform. 80, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2017, 65,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.65."},{"key":"atypb21","unstructured":"F. V. Fomin, D. Lokshtanov, F. Panolan, S. Saurabh, and M. Zehavi,\n                      ETH-tight algorithms for long path and cycle on unit disk graphs\n                      , in 36th International Symposium on Computational Geometry, SOCG 2020, LIPIcs Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020, 44,https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2020.44."},{"key":"atypb22","first-page":"1563","author":"Fomin F. V.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.05.003"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0205049"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000260"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079336"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0211056"},{"key":"atypb32","first-page":"120","volume":"2010","author":"Ito H.","year":"2010","journal-title":"ISORA"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9394-8"},{"key":"atypb34","unstructured":"S. Kisfaludi-Bak,\n                      ETH-Tight Algorithms for Geometric Network Problems\n                      , PhD thesis, Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, Eindhoven, The Netherlands, 2019,https:\/\/research.tue.nl\/en\/publications\/eth-tight-algorithms-for-geometric-network-problems."},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"S. Kisfaludi-Bak and T. C. van der Zanden,\n                      On the exact complexity of Hamiltonian cycle and $q$-colouring in disk graphs\n                      , in Proceedings 10th International Conference on Algorithms and Complexity, CIAC 2017, D. Fotakis, A. Pagourtzis, and V. T. Paschos, eds., Lecture Notes in Computer Science 10236, Springer, Cham, Switzerland, 2017, pp. 369-380,https:\/\/doi.org\/10.1007\/978-3-319-57586-5_31.","DOI":"10.1007\/978-3-319-57586-5_31"},{"key":"atypb36","first-page":"116","volume":"38","author":"K\u00f6nig D.","year":"1931","journal-title":"Mat. Fiz. Lapok"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"atypb40","first-page":"28","author":"Marx D.","year":"2013","journal-title":"Berlin"},{"key":"atypb41","first-page":"865","author":"Marx D.","year":"2015","journal-title":"Germany"},{"key":"atypb42","first-page":"67","author":"Marx D.","year":"2014","journal-title":"New York"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.08.006"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90023-1"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"W. D. Smith and N. C. Wormald,\n                      Geometric separator theorems and applications\n                      , in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, IEEE Computer Society, Los Alamitos, CA, 1998, pp. 232-243,https:\/\/doi.org\/10.1109\/SFCS.1998.743449.","DOI":"10.1109\/SFCS.1998.743449"},{"key":"atypb47","unstructured":"E. Speckenmeyer,\n                      Untersuchungen zum Feedback-vertex-set-Problem in ungerichteten Graphen\n                      , PhD thesis, University of Paderborn, Paderborn, Germany, 1983,http:\/\/d-nb.info\/831085894."},{"key":"atypb48","first-page":"58","volume":"1976","author":"Thompson C. D.","year":"1976","journal-title":"STOC"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/359461.359481"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1226-x"},{"key":"atypb52","first-page":"185","author":"Woeginger G. J.","year":"2003","journal-title":"Berlin"},{"key":"atypb53","unstructured":"T. C. van der Zanden,\n                      Theory and Practical Applications of Treewidth\n                      , PhD thesis, Universiteit Utrecht, Department of Information and Computing Sciences, Utrecht, The Netherlands, 2019,https:\/\/dspace.library.uu.nl\/handle\/1874\/381134."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1320870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:26:40Z","timestamp":1787336800000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1320870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":53,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/20M1320870"],"URL":"https:\/\/doi.org\/10.1137\/20m1320870","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}