{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:55:05Z","timestamp":1781078105785,"version":"3.54.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T00:00:00Z","timestamp":1678320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["853234"],"award-info":[{"award-number":["853234"]}]},{"name":"European Unions Horizon 2020 research and innovation programme","award":["714704"],"award-info":[{"award-number":["714704"]}]},{"DOI":"10.13039\/501100014434","name":"Polish National Agency for Academic Exchange","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014434","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>We describe a polynomial-time algorithm which, given a graph<jats:italic>G<\/jats:italic>with treewidth<jats:italic>t<\/jats:italic>, approximates the pathwidth of<jats:italic>G<\/jats:italic>to within a ratio of<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(t\\sqrt {\\log t})\\)<\/jats:tex-math><\/jats:inline-formula>. This is the first algorithm to achieve an<jats:italic>f(t)<\/jats:italic>-approximation for some function<jats:italic>f<\/jats:italic>.<\/jats:p><jats:p>Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least<jats:italic>th<\/jats:italic>+2 has treewidth at least<jats:italic>t<\/jats:italic>or contains a subdivision of a complete binary tree of height<jats:italic>h<\/jats:italic>+1. The bound<jats:italic>th<\/jats:italic>+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with<jats:italic>c<\/jats:italic>=2), the following conjecture of Kawarabayashi and Rossman (SODA\u201918): there exists a universal constant<jats:italic>c<\/jats:italic>such that every graph with pathwidth \u03a9(<jats:italic>k<\/jats:italic><jats:sup>c<\/jats:sup>) has treewidth at least<jats:italic>k<\/jats:italic>or contains a subdivision of a complete binary tree of height<jats:italic>k<\/jats:italic>.<\/jats:p><jats:p>Our main technical algorithm takes a graph<jats:italic>G<\/jats:italic>and some (not necessarily optimal) tree decomposition of<jats:italic>G<\/jats:italic>of width<jats:italic>t<\/jats:italic>\u2032 in the input, and it computes in polynomial time an integer<jats:italic>h<\/jats:italic>, a certificate that<jats:italic>G<\/jats:italic>has pathwidth at least<jats:italic>h<\/jats:italic>, and a path decomposition of<jats:italic>G<\/jats:italic>of width at most (<jats:italic>t<\/jats:italic>\u2032+1)<jats:italic>h<\/jats:italic>+1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height<jats:italic>h<\/jats:italic>. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC\u201905) for treewidth.<\/jats:p>","DOI":"10.1145\/3576044","type":"journal-article","created":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T12:22:21Z","timestamp":1670934141000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Approximating Pathwidth for Graphs of Small Treewidth"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9878-8750","authenticated-orcid":false,"given":"Carla","family":"Groenland","sequence":"first","affiliation":[{"name":"Utrecht University, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7157-6694","authenticated-orcid":false,"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8371-425X","authenticated-orcid":false,"given":"Wojciech","family":"Nadara","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5761-2564","authenticated-orcid":false,"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[{"name":"Jagiellonian University, Krak\u00f3w, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005369"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90068-U"},{"issue":"1","key":"e_1_3_2_5_2","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender Hans L.","year":"1992","unstructured":"Hans L. Bodlaender. 1992. A tourist guide through treewidth. Acta Cybernetica 11, 1\u20132 (1992), 1\u201321.","journal-title":"Acta Cybernetica"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/978-3-642-30891-8_12","volume-title":"The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday","author":"Bodlaender Hans L.","year":"2012","unstructured":"Hans L. Bodlaender. 2012. Fixed-parameter tractability of treewidth and pathwidth. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer, Berlin, 196\u2013227."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00001-9"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00190-5"},{"issue":"5","key":"e_1_3_2_11_2","first-page":"Article No. 40","article-title":"Polynomial bounds for the grid-minor theorem","volume":"63","author":"Chekuri Chandra","year":"2016","unstructured":"Chandra Chekuri and Julia Chuzhoy. 2016. Polynomial bounds for the grid-minor theorem. J. ACM 63, 5 (2016), Article No. 40.","journal-title":"J. ACM"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.09.010"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M128819X"},{"key":"e_1_3_2_14_2","series-title":"Graph Structure Theory: Proceedings of a Joint Summer Research Conference on Graph Minors","first-page":"677","volume":"147","author":"Dean Nathaniel","year":"1993","unstructured":"Nathaniel Dean. 1993. Open problems. In Graph Structure Theory: Proceedings of a Joint Summer Research Conference on Graph Minors, Neil Robertson and Paul Seymour (Eds.). Contemporary Mathematics, Vol. 147. American Mathematical Society, Providence, 677\u2013688."},{"key":"e_1_3_2_15_2","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory (4th ed.)","author":"Diestel Reinhard","year":"2010","unstructured":"Reinhard Diestel. 2010. Graph Theory (4th ed.). Graduate Texts in Mathematics, Vol. 173. Springer, Berlin."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.06.004"},{"key":"e_1_3_2_18_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/11682462_45","volume-title":"LATIN 2006: Theoretical Informatics","author":"Fraigniaud Pierre","year":"2006","unstructured":"Pierre Fraigniaud and Nicolas Nisse. 2006. Connected treewidth and connected graph searching. In LATIN 2006: Theoretical Informatics, Jos\u00e9 R. Correa, Alejandro Hevia, and Marcos Kiwi (Eds.). Lecture Notes in Computer Science, Vol. 3887. Springer, Berlin, 479\u2013490."},{"issue":"3","key":"e_1_3_2_19_2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","article-title":"On the pathwidth of chordal graphs","volume":"45","author":"Gusted Jens","year":"1993","unstructured":"Jens Gusted. 1993. On the pathwidth of chordal graphs. Discrete Applied Mathematics 45, 3 (1993), 233\u2013248.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01462229"},{"key":"e_1_3_2_21_2","volume-title":"Graph minors and tree decompositions","author":"Hickingbotham Robert","year":"2019","unstructured":"Robert Hickingbotham. 2019. Graph minors and tree decompositions. Bachelor\u2019s thesis. School of Mathematics, Monash University, Melbourne."},{"issue":"1","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"39","DOI":"10.6028\/jres.076B.002","article-title":"Three results for trees, using mathematical induction","volume":"76","author":"Horn William A.","year":"1972","unstructured":"William A. Horn. 1972. Three results for trees, using mathematical induction. Journal of Research of the National Bureau of Standards, Series B: Mathematical Sciences 76B, 1\u20132 (1972), 39\u201343.","journal-title":"Journal of Research of the National Bureau of Standards, Series B: Mathematical Sciences"},{"issue":"4","key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"1449","DOI":"10.4171\/JEMS\/1133","article-title":"A polynomial excluded-minor approximation of treedepth","volume":"24","author":"Kawarabayashi Ken-ichi","year":"2022","unstructured":"Ken-ichi Kawarabayashi and Benjamin Rossman. 2022. A polynomial excluded-minor approximation of treedepth. Journal of the European Mathematical Society 24, 4 (2022), 1449\u20131470.","journal-title":"Journal of the European Mathematical Society"},{"key":"e_1_3_2_24_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-57273-2_61","volume-title":"Algorithms\u2014ESA\u201993","author":"Kloks Ton","year":"1993","unstructured":"Ton Kloks, Hans L. Bodlaender, Haiko M\u00fcller, and Dieter Kratsch. 1993. Computing treewidth and minimum fill-in: All you need are the minimal separators. In Algorithms\u2014ESA\u201993, Thomas Lengauer (Ed.). Lecture Notes in Computer Science, Vol. 726. Springer, Berlin, 260\u2013271."},{"key":"e_1_3_2_25_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-59071-4_41","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Kloks Ton","year":"1995","unstructured":"Ton Kloks, Dieter Kratsch, and Haiko M\u00fcller. 1995. Dominoes. In Graph-Theoretic Concepts in Computer Science, Ernst W. Mayr, Gunther Schmidt, and Gottfried Tinhofer (Eds.). Lecture Notes in Computer Science, Vol. 903. Springer, Berlin, 106\u2013120."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21825"},{"issue":"1","key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","article-title":"Min Cut is NP-complete for edge weighted trees","volume":"58","author":"Monien Burkhard","year":"1988","unstructured":"Burkhard Monien and Ivan Hal Sudborough. 1988. Min Cut is NP-complete for edge weighted trees. Theoretical Computer Science 58, 1 (1988), 209\u2013229.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_29_2","volume-title":"Die Baumweite von Graphen als ein Ma\u00df f\u00fcr die Kompliziertheit algorithmischer Probleme","author":"Scheffler Petra","year":"1989","unstructured":"Petra Scheffler. 1989. Die Baumweite von Graphen als ein Ma\u00df f\u00fcr die Kompliziertheit algorithmischer Probleme. Ph.D. Dissertation. Akademie der Wissenschaften der DDR, Berlin."},{"key":"e_1_3_2_30_2","volume-title":"Personal communication","author":"Wood David R.","year":"2013","unstructured":"David R. Wood. 2013. Personal communication. (2013)."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3576044","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3576044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:39Z","timestamp":1750182579000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3576044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,9]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3576044"],"URL":"https:\/\/doi.org\/10.1145\/3576044","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,9]]},"assertion":[{"value":"2021-03-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}