{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:14Z","timestamp":1781077514055,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T00:00:00Z","timestamp":1719964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"\n We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set\n \n \\(\\mathcal{D}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n unit disks inducing a unit-disk graph\n \n \\(G_{\\mathcal{D}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and a number\n \n \\(p\\in[n]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , one can partition\n \n \\(\\mathcal{D}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n into\n \n \\(p\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n subsets\n \n \\(\\mathcal{D}_{1},\\dots,\\mathcal{D}_{p}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that for every\n \n \\(i\\in[p]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and every\n \n \\(\\mathcal{D}^{\\prime}\\subseteq\\mathcal{D}_{i}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , the graph obtained from\n \n \\(G_{\\mathcal{D}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n by contracting all edges between the vertices in\n \n \\(\\mathcal{D}_{i}\\backslash\\mathcal{D}^{\\prime}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n admits a tree decomposition in which each bag consists of\n \n \\(O(p+|\\mathcal{D}^{\\prime}|)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n cliques. Our theorem can be viewed as an analog for unit-disk graphs of the structural theorems for planar graphs and almost-embeddable graphs proved recently by Marx et al. [SODA \u201922] and Bandyapadhyay et al. [SODA \u201922]. By applying our structural theorem, we give several new combinatorial and algorithmic results for unit-disk graphs. On the combinatorial side, we obtain the first Contraction Decomposition Theorem for unit-disk graphs, resolving an open question in the work by Panolan et al. [SODA \u201919]. On the algorithmic side, we obtain a new algorithm for bipartization (also known as odd cycle transversal) on unit-disk graphs, which runs in\n \n \\(2^{O(\\sqrt{k}\\log k)}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time, where\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denotes the solution size. Our algorithm significantly improves the previous slightly subexponential-time algorithm given by Lokshtanov et al. [SODA \u201922] which runs in\n \n \\(2^{O(k^{27\/28})}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time. We also show that the problem cannot be solved in\n \n \\(2^{o(\\sqrt{k})}\\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time assuming the Exponential Time Hypothesis, which implies that our algorithm is almost optimal.\n <\/jats:p>","DOI":"10.1145\/3656042","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T05:40:22Z","timestamp":1712641222000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8875-0102","authenticated-orcid":false,"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[{"name":"Portland State University, Portland, Oregon, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8711-1170","authenticated-orcid":false,"given":"William","family":"Lochet","sequence":"additional","affiliation":[{"name":"LIRMM, Universit\u00e9 de Montpellier, CNRS, Montpellier, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7015-1988","authenticated-orcid":false,"given":"Jie","family":"Xue","sequence":"additional","affiliation":[{"name":"New York University Shanghai, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,7,3]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"573","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC \u201905)","author":"Agarwal Amit","year":"2005","unstructured":"Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. 2005. \\(o(\\sqrt{\\log n})\\) approximation algorithms for min Uncut, min 2CNF deletion, and directed cut problems. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC \u201905). 573\u2013581."},{"issue":"4","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1016\/S0022-0000(03)00072-2","article-title":"Graph separators: A parameterized view","volume":"67","author":"Alber Jochen","year":"2003","unstructured":"Jochen Alber, Henning Fernau, and Rolf Niedermeier. 2003. Graph separators: A parameterized view. J. Comput. Syst. Sci. 67, 4 (2003), 808\u2013832.","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","article-title":"Geometric separation and exact solutions for the parameterized independent set problem on disk graphs","volume":"52","author":"Alber Jochen","year":"2004","unstructured":"Jochen Alber and Jir\u00ed Fiala. 2004. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52, 2 (2004), 134\u2013151.","journal-title":"J. Algorithms"},{"key":"e_1_3_2_5_2","first-page":"47:1","volume-title":"Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC \u201921)","volume":"212","author":"An Shinwoo","year":"2021","unstructured":"Shinwoo An and Eunjin Oh. 2021. Feedback vertex set on geometric intersection graphs. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC \u201921). Hee-Kap Ahn and Kunihiko Sadakane (Eds.), LIPIcs, Vol. 212, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 47:1\u201347:12."},{"issue":"1","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s00454-018-9968-1","article-title":"On forbidden induced subgraphs for unit disk graphs","volume":"60","author":"Atminas Aistis","year":"2018","unstructured":"Aistis Atminas and Viktor Zamaraev. 2018. On forbidden induced subgraphs for unit disk graphs. Discrete Comput. Geom. 60, 1 (2018), 57\u201397.","journal-title":"Discrete Comput. Geom."},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"2063","DOI":"10.1137\/1.9781611977073.82","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922).","author":"Bandyapadhyay Sayan","year":"2022","unstructured":"Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue. 2022. Subexponential parameterized algorithms for cut and cycle hitting problems on \\(H\\) -minor-free graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922). 2063\u20132084."},{"issue":"2","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1137\/0221016","article-title":"Partitioning planar graphs","volume":"21","author":"Bui Thang Nguyen","year":"1992","unstructured":"Thang Nguyen Bui and Andrew Peck. 1992. Partitioning planar graphs. SIAM J. Comput. 21, 2 (1992), 203\u2013215.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/j.comgeo.2014.12.003","article-title":"Shortest paths in intersection graphs of unit disks","volume":"48","author":"Cabello Sergio","year":"2015","unstructured":"Sergio Cabello and Miha Jejcic. 2015. Shortest paths in intersection graphs of unit disks. Comput. Geom. 48, 4 (2015), 360\u2013367.","journal-title":"Comput. Geom."},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-319-62127-2_22","volume-title":"Proceedings of the Workshop on Algorithms and Data Structures (WADS \u201917)","author":"Chan Timothy M.","year":"2017","unstructured":"Timothy M. Chan and Dimitrios Skrepetos. 2017. All-pairs shortest paths in geometric intersection graphs. In Proceedings of the Workshop on Algorithms and Data Structures (WADS \u201917). Springer, 253\u2013264."},{"issue":"2","key":"e_1_3_2_11_2","first-page":"3","article-title":"Approximate shortest paths and distance oracles in weighted unit-disk graphs","volume":"10","author":"Chan Timothy M.","year":"2019","unstructured":"Timothy M. Chan and Dimitrios Skrepetos. 2019. Approximate shortest paths and distance oracles in weighted unit-disk graphs. J. Comput. Geom. 10, 2 (2019), 3\u201320.","journal-title":"J. Comput. Geom."},{"issue":"1","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","article-title":"Unit disk graphs","volume":"86","author":"Clark Brent N.","year":"1990","unstructured":"Brent N. Clark, Charles J. Colbourn, and David S. Johnson. 1990. Unit disk graphs. Discrete Math. 86, 1\u20133 (1990), 165\u2013177.","journal-title":"Discrete Math."},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"Cygan Marek","year":"2015","unstructured":"Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1145\/3188745.3188854","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201918)","author":"Berg Mark de","year":"2018","unstructured":"Mark de Berg, Hans L. Bodlaender, S\u00e1ndor Kisfaludi-Bak, D\u00e1niel Marx, and Tom C. van der Zanden. 2018. A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201918). 574\u2013586."},{"issue":"6","key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","article-title":"Subexponential parameterized algorithms on bounded-genus graphs and \\(H\\) -minor-free graphs","volume":"52","author":"Demaine Erik D.","year":"2005","unstructured":"Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. 2005. Subexponential parameterized algorithms on bounded-genus graphs and \\(H\\) -minor-free graphs. J. ACM 52, 6 (2005), 866\u2013893.","journal-title":"J. ACM"},{"key":"e_1_3_2_16_2","first-page":"441","volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC \u201911)","author":"Demaine Erik D.","year":"2011","unstructured":"Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-Ichi Kawarabayashi. 2011. Contraction decomposition in \\(H\\) -minor-free graphs and algorithmic applications. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC \u201911). 441\u2013450."},{"issue":"5","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/s00493-010-2341-5","article-title":"Approximation algorithms via contraction decomposition","volume":"30","author":"Demaine Erik D.","year":"2010","unstructured":"Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar. 2010. Approximation algorithms via contraction decomposition. Combinatorica 30, 5, (2010), 533\u2013552.","journal-title":"Combinatorica"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.ic.2013.11.006","article-title":"Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs","volume":"233","author":"Dorn Frederic","year":"2013","unstructured":"Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. 2013. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Inf. Comput. 233 (2013), 60\u201370.","journal-title":"Inf. Comput."},{"issue":"7","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1016\/j.dam.2007.08.013","article-title":"Planar graph bipartization in linear time","volume":"156","author":"Fiorini Samuel","year":"2008","unstructured":"Samuel Fiorini, Nadia Hardy, Bruce Reed, and Adrian Vetta. 2008. Planar graph bipartization in linear time. Discrete Appl. Math. 156, 7 (2008), 1175\u20131180.","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"e_1_3_2_20_2","first-page":"21:1","article-title":"Subexponential algorithms for rectilinear Steiner tree and arborescence problems","volume":"16","author":"Fomin Fedor V.","year":"2020","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, Sudeshna Kolay, Fahad Panolan, and Saket Saurabh. 2020. Subexponential algorithms for rectilinear Steiner tree and arborescence problems. ACM Trans. Algorithms, 16, 2 (2020), 21:1\u201321:37.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/FOCS.2016.62","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS \u201916)","author":"Fomin Fedor V.","year":"2016","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. (2016). Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS \u201916). Irit Dinur (Ed.), Hyatt Regency, IEEE Computer Society, 515\u2013524."},{"key":"e_1_3_2_22_2","first-page":"60:1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919)","volume":"132","author":"Fomin Fedor V.","year":"2019","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2019. Decomposition of map graphs with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919). Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.), LIPIcs, Vol. 132, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 60:1\u201360:15."},{"issue":"4","key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1007\/s00454-018-00054-x","article-title":"Finding, hitting and packing cycles in subexponential time on unit disk graphs","volume":"62","author":"Fomin Fedor V.","year":"2019","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2019. Finding, hitting and packing cycles in subexponential time on unit disk graphs. Discret. Comput. Geom. 62, 4 (2019), 879\u2013911.","journal-title":"Discret. Comput. Geom."},{"key":"e_1_3_2_24_2","first-page":"44:1","volume-title":"Proceedings of the 36th International Symposium on Computational Geometry (SoCG \u201920)","volume":"164","author":"Fomin Fedor V.","year":"2020","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2020. ETH-tight algorithms for long path and cycle on unit disk graphs. In Proceedings of the 36th International Symposium on Computational Geometry (SoCG \u201920). Sergio Cabello and Danny Z. Chen (Eds.), LIPIcs, Vol. 164, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 44:1\u201344:18."},{"issue":"2","key":"e_1_3_2_25_2","first-page":"10:1","article-title":"Excluded grid minors and efficient polynomial-time approximation schemes","volume":"65","author":"Fomin Fedor V.","year":"2018","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. 2018. Excluded grid minors and efficient polynomial-time approximation schemes. J. ACM 65, 2 (2018), 10:1\u201310:44.","journal-title":"J. ACM"},{"issue":"1","key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/S0097539703436357","article-title":"Well-separated pair decomposition for the unit-disk graph metric and its applications","volume":"35","author":"Gao Jie","year":"2005","unstructured":"Jie Gao and Li Zhang. 2005. Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J. Comput. 35, 1 (2005), 151\u2013169.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/PL00009810","article-title":"Primal-dual approximation algorithms for feedback problems in planar graphs","volume":"18","author":"Goemans Michel X.","year":"1998","unstructured":"Michel X. Goemans and David P. Williamson. 1998. Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica 18, 1 (1998), 37\u201359.","journal-title":"Combinatorica"},{"issue":"1","key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-0010-x","article-title":"Algorithms for graphs embeddable with few crossings per edge","volume":"49","author":"Grigoriev Alexander","year":"2007","unstructured":"Alexander Grigoriev and Hans L. Bodlaender. 2007. Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49, 1 (2007), 1\u201311.","journal-title":"Algorithmica"},{"issue":"1","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.disopt.2010.05.003","article-title":"FPT algorithms for path-transversal and cycle-transversal problems","volume":"8","author":"Guillemot Sylvain","year":"2011","unstructured":"Sylvain Guillemot. 2011. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optim. 8, 1 (2011), 61\u201371.","journal-title":"Discrete Optim."},{"key":"e_1_3_2_30_2","article-title":"Contraction and minor graph decomposition and their algorithmic applications","author":"Hajiaghayi MohammadTaghi","year":"2016","unstructured":"MohammadTaghi Hajiaghayi. 2016. Contraction and minor graph decomposition and their algorithmic applications. Filmed Talk at Microsoft Research.","journal-title":"Filmed Talk at Microsoft Research"},{"key":"e_1_3_2_31_2","first-page":"1497","volume-title":"Proc. IEEE","volume":"68","author":"Hale William K.","year":"1980","unstructured":"William K. Hale. 1980. Frequency assignment: Theory and applications. Proc. IEEE 68, 12 (1980), 1497\u20131514."},{"issue":"2","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.7155\/jgaa.00177","article-title":"Algorithm engineering for optimal graph bipartization","volume":"13","author":"H\u00fcffner Falk","year":"2009","unstructured":"Falk H\u00fcffner. 2009. Algorithm engineering for optimal graph bipartization. J. Graph Algorithms Appl. 13, 2 (2009), 77\u201398.","journal-title":"J. Graph Algorithms Appl."},{"key":"e_1_3_2_33_2","first-page":"39:1","volume-title":"Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS \u201919)","volume":"126","author":"Jansen Bart M. P.","unstructured":"Bart M. P. Jansen, Marcin Pilipczuk, and Erik Jan van Leeuwen. A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS \u201919). Rolf Niedermeier and Christophe Paul (Eds.), LIPIcs, Vol. 126, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 39:1\u201339:18."},{"key":"e_1_3_2_34_2","first-page":"365","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201910)","author":"Kawarabayashi Ken-Ichi","year":"2010","unstructured":"Ken-Ichi Kawarabayashi and Bruce Reed. 2010. An (almost) linear time algorithm for odd cycles transversal. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201910). SIAM, 365\u2013378."},{"key":"e_1_3_2_35_2","first-page":"749","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC \u201906)","author":"Klein Philip N.","year":"2006","unstructured":"Philip N. Klein. 2006. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC \u201906). 749\u2013756."},{"issue":"6","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"1926","DOI":"10.1137\/060649562","article-title":"A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights","volume":"37","author":"Klein Philip N.","year":"2008","unstructured":"Philip N. Klein. 2008. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37, 6 (2008), 1926\u20131952.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/978-3-642-31594-7_48","volume-title":"Proceedings of the 39th International Colloquium Automata, Languages, and Programming (ICALP \u201912)","volume":"7391","author":"Klein Philip N.","year":"2012","unstructured":"Philip N. Klein and D\u00e1niel Marx. 2012. Solving planar \\(k\\) -terminal cut in \\(O(n^{c\\sqrt{k}})\\) time. In Proceedings of the 39th International Colloquium Automata, Languages, and Programming (ICALP \u201912). Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (Eds.), Lecture Notes in Computer Science, Vol. 7391, Springer, 569\u2013580."},{"key":"e_1_3_2_38_2","first-page":"1812","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914)","author":"Klein Philip N.","year":"2014","unstructured":"Philip N. Klein and D\u00e1niel Marx. 2014. A subexponential parameterized algorithm for subset TSP on planar graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201914). Chandra Chekuri, editor, SIAM, 1812\u20131830."},{"issue":"4","key":"e_1_3_2_39_2","first-page":"20:1","article-title":"Compression via matroids: A randomized polynomial kernel for odd cycle transversal","volume":"10","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch and Magnus Wahlstr\u00f6m. 2014. Compression via matroids: A randomized polynomial kernel for odd cycle transversal. ACM Trans. Algorithms 10, 4 (2014), 20:1\u201320:15.","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2566616","article-title":"Faster parameterized algorithms using linear programming","volume":"11","author":"Lokshtanov Daniel","year":"2014","unstructured":"Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2014. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms (TALG) 11, 2 (2014), 1\u201331.","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"2005","DOI":"10.1137\/1.9781611977073.80","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922)","author":"Lokshtanov Daniel","year":"2022","unstructured":"Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. 2022. Subexponential parameterized algorithms on disk graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922). 2005\u20132031."},{"key":"e_1_3_2_42_2","first-page":"424","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS \u201912)","volume":"18","author":"Lokshtanov Daniel","year":"2012","unstructured":"Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlstr\u00f6m. 2012. Subexponential parameterized odd cycle transversal on planar graphs. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS \u201912). Deepak D\u2019Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan (Eds.), LIPIcs, Vol. 18, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 424\u2013434."},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"2085","DOI":"10.1137\/1.9781611977073.83","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922)","author":"Marx D\u00e1niel","year":"2022","unstructured":"D\u00e1niel Marx, Pranabendu Misra, Daniel Neuen, and Prafullkumar Tale. 2022. A framework for parameterized subexponential algorithms for generalized cycle hitting problems on planar graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201922). 2085\u20132127."},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1109\/FOCS.2018.00052","volume-title":"Proccedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201918)","author":"Marx D\u00e1niel","year":"2018","unstructured":"D\u00e1niel Marx, Marcin Pilipczuk, and Michal Pilipczuk. 2018. On subexponential parameterized algorithms for steiner tree and directed subset TSP on planar graphs. In Proccedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201918). Mikkel Thorup (Ed.), IEEE Computer Society, 474\u2013484."},{"key":"e_1_3_2_45_2","first-page":"865","volume-title":"Proccedings of the Algorithms 23rd Annual European Symposium (ESA \u201915)","volume":"9294","author":"Marx D\u00e1niel","year":"2015","unstructured":"D\u00e1niel Marx and Michal Pilipczuk. 2015. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In Proccedings of the Algorithms 23rd Annual European Symposium (ESA \u201915). Nikhil Bansal and Irene Finocchi (Eds.), Lecture Notes in Computer Science, Vol. 9294, Springer, 865\u2013877."},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1145\/3357713.3384261","volume-title":"Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201920)","author":"Nederlof Jesper","year":"2020","unstructured":"Jesper Nederlof. 2020. Detecting and counting small patterns in planar graphs in subexponential parameterized time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201920). Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy (Eds.), ACM, 1293\u20131306."},{"issue":"11","key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0898-1221(97)00225-3","article-title":"The hidden algorithm of Ore\u2019s theorem on Hamiltonian cycles","volume":"34","author":"Palmer Emily","year":"1997","unstructured":"Emily Palmer. The hidden algorithm of Ore\u2019s theorem on Hamiltonian cycles. Comput. Math. Appl. 34, 11 (1997), 113\u2013119.","journal-title":"Comput. Math. Appl."},{"key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1137\/1.9781611975482.64","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201919)","author":"Panolan Fahad","year":"2019","unstructured":"Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2019. Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201919). Timothy M. Chan. (Ed.), SIAM, 1035\u20131054."},{"key":"e_1_3_2_49_2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-030-10564-8_2","volume-title":"Proceedings of the 13th International Conference Algorithms and Computation (WALCOM \u201919)","volume":"11355","author":"Panolan Fahad","year":"2019","unstructured":"Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2019. Parameterized computational geometry via decomposition theorems. In Proceedings of the 13th International Conference Algorithms and Computation (WALCOM \u201919). Gautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya, and Shin-Ichi Nakano. (Eds.), Lecture Notes in Computer Science, Vol. 11355, Springer, 15\u201327."},{"issue":"4","key":"e_1_3_2_50_2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","article-title":"Finding odd cycle transversals","volume":"32","author":"Reed Bruce","year":"2004","unstructured":"Bruce Reed, Kaleigh Smith, and Adrian Vetta. 2004. Finding odd cycle transversals. Oper. Res. Lett. 32, 4 (2004), 299\u2013301.","journal-title":"Oper. Res. Lett."},{"key":"e_1_3_2_51_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.tcs.2011.09.014","article-title":"Faster approximation schemes and parameterized algorithms on (odd-) \\(H\\) -minor-free graphs","volume":"417","author":"Tazari Siamak","year":"2012","unstructured":"Siamak Tazari. 2012. Faster approximation schemes and parameterized algorithms on (odd-) \\(H\\) -minor-free graphs. Theor. Comput. Sci. 417 (2012), 95\u2013107.","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"e_1_3_2_52_2","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1007\/s00454-020-00219-7","article-title":"Near-optimal algorithms for shortest paths in weighted unit-disk graphs","volume":"64","author":"Wang Haitao","year":"2020","unstructured":"Haitao Wang and Jie Xue. 2020. Near-optimal algorithms for shortest paths in weighted unit-disk graphs. Discrete Comput. Geom. 64, 4 (2020), 1141\u20131166.","journal-title":"Discrete Comput. Geom."},{"key":"e_1_3_2_53_2","first-page":"253","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computingcomputing (STOC \u201978)","author":"Yannakakis Mihalis","year":"1978","unstructured":"Mihalis Yannakakis. 1978. Node-and edge-deletion NP-complete problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computingcomputing (STOC \u201978). 253\u2013264."},{"issue":"3","key":"e_1_3_2_54_2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1109\/T-VT.1984.23998","article-title":"Outage probability in mobile telephony with directive antennas and macrodiversity","volume":"33","author":"Yeh Yu-Shuan","year":"1984","unstructured":"Yu-Shuan Yeh, Joanne C. Wilson, and Stuart C. Schwartz. 1984. Outage probability in mobile telephony with directive antennas and macrodiversity. IEEE Trans. Veh. Technol. 33, 3 (1984), 123\u2013127.","journal-title":"IEEE Trans. Veh. Technol."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656042","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:48Z","timestamp":1750291428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,3]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3656042"],"URL":"https:\/\/doi.org\/10.1145\/3656042","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,3]]},"assertion":[{"value":"2022-12-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}