{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:10Z","timestamp":1750295410726,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T00:00:00Z","timestamp":1705881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["759557"],"award-info":[{"award-number":["759557"]}]},{"name":"Academy of Finland Research Fellowship","award":["310415"],"award-info":[{"award-number":["310415"]}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001665","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":[[2024,1,31]]},"abstract":"\n The fundamental Sparsest Cut problem takes as input a graph\n G<\/jats:italic>\n together with edge capacities and demands and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For\n n<\/jats:italic>\n -vertex graphs\u00a0\n G<\/jats:italic>\n of treewidth\u00a0\n k<\/jats:italic>\n , Chlamt\u00e1\u010d, Krauthgamer, and Raghavendra (APPROX\u201910) presented an algorithm that yields a factor-\n \n \\(2^{2^k}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n approximation in time\n \n \\(2^{O(k)} \\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Later, Gupta, Talwar, and Witmer (STOC\u201913) showed how to obtain a 2-approximation algorithm with a blown-up runtime of\n \n \\(n^{O(k)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-2 approximation in time\n \n \\(2^{O(k)} \\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n In this article, we make significant progress towards this goal via the following results:\n \n \n (i)<\/jats:label>\n \n A factor-\n \n \\(O(k^2)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n approximation that runs in time\n \n \\(2^{O(k)} \\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , directly improving the work of Chlamt\u00e1\u010d et\u00a0al. while keeping the runtime single-exponential in\n k<\/jats:italic>\n .\n <\/jats:p>\n <\/jats:list-item>\n \n (ii)<\/jats:label>\n \n For any\n \n \\(\\varepsilon \\in (0,1]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , a factor-\n \n \\(O(1\/\\varepsilon ^2)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n approximation whose runtime is\n \n \\(2^{O(k^{1+\\varepsilon }\/\\varepsilon)} \\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , implying a constant-factor approximation whose runtime is nearly single-exponential in\n k<\/jats:italic>\n and a factor-\n \n \\(O(\\log ^2 k)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n approximation in time\n \n \\(k^{O(k)} \\cdot n^{O(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>\n \n Key to these results is a new measure of a tree decomposition that we call\n combinatorial diameter<\/jats:italic>\n , which may be of independent interest.\n <\/jats:p>","DOI":"10.1145\/3632623","type":"journal-article","created":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T11:27:39Z","timestamp":1699961259000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2833-0472","authenticated-orcid":false,"given":"Parinya","family":"Chalermsook","sequence":"first","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0124-0789","authenticated-orcid":false,"given":"Matthias","family":"Kaul","sequence":"additional","affiliation":[{"name":"Hamburg University of Technology, Institute for Algorithms and Complexity, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4721-5354","authenticated-orcid":false,"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[{"name":"Hamburg University of Technology, Institute for Algorithms and Complexity, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2601-6452","authenticated-orcid":false,"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[{"name":"University of Sheffield, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3999-7827","authenticated-orcid":false,"given":"Sumedha","family":"Uniyal","sequence":"additional","affiliation":[{"name":"Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2224-2185","authenticated-orcid":false,"given":"Daniel","family":"Vaz","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure Paris and Universit\u00e9 Paris Cit\u00e9, CNRS, IRIF, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-07-00573-5"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2004.03.002"},{"key":"e_1_3_2_5_2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"WG\u201988","author":"Bodlaender Hans L.","year":"1988","unstructured":"Hans L. Bodlaender. 1988. NC-Algorithms for graphs with small treewidth. In WG\u201988(Lecture Notes in Computer Science, Vol. 344). 1\u201310."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.12.008"},{"key":"e_1_3_2_7_2","series-title":"APPROX-RANDOM\u201918","first-page":"8:1\u20138:19","volume":"116","author":"Chalermsook Parinya","year":"2018","unstructured":"Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, and Daniel Vaz. 2018. Survivable network design for group connectivity in low-treewidth graphs. In APPROX-RANDOM\u201918(Leibniz International Proceedings in Informatics, Vol. 116). 8:1\u20138:19."},{"key":"e_1_3_2_8_2","first-page":"737","volume-title":"SODA\u201917","author":"Chalermsook Parinya","year":"2017","unstructured":"Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, and Daniel Vaz. 2017. Beyond metric embedding: Approximating group Steiner trees on bounded treewidth graphs. In SODA\u201917. 737\u2013751."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102417379"},{"key":"e_1_3_2_11_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/978-3-642-15369-3_10","volume-title":"APPROX\/RANDOM\u201910","author":"Chlamt\u00e1\u010d Eden","year":"2010","unstructured":"Eden Chlamt\u00e1\u010d, Robert Krauthgamer, and Prasad Raghavendra. 2010. Approximating sparsest cut in graphs of bounded treewidth. In APPROX\/RANDOM\u201910(Lecture Notes in Computer Science, Vol. 6302). 124\u2013137."},{"key":"e_1_3_2_12_2","unstructured":"Eden Chlamt\u00e1\u010d Robert Krauthgamer and Prasad Raghavendra. 2010. Approximating sparsest cut in graphs of bounded treewidth. CoRR abs\/1006.3970 (2010). Retrieved from https:\/\/arxiv.org\/abs\/1006.3970"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502795"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451103"},{"key":"e_1_3_2_15_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-031-06901-7_9","volume-title":"IPCO\u201922","author":"Cohen-Addad Vincent","year":"2022","unstructured":"Vincent Cohen-Addad, Tobias M\u00f6mke, and Victor Verdugo. 2022. A 2-approximation for the bounded treewidth sparsest cut Problem in FPT time. In IPCO\u201922(Lecture Notes in Computer Science, Vol. 13265). 112\u2013125."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488644"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_3_2_20_2","first-page":"184","volume-title":"FOCS\u201921","author":"Korhonen Tuukka","year":"2022","unstructured":"Tuukka Korhonen. 2022. A single-exponential time 2-approximation algorithm for treewidth. In FOCS\u201921. 184\u2013192."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_22_2","unstructured":"Anupam Gupta and Amitabh Basu. 2008. Lecture 19: Sparsest Cut and \\(\\ell _1\\) Embeddings. Retrieved from https:\/\/www.cs.cmu.edu\/anupamg\/adv-approx\/lecture19.pdf"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2685-8"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_25_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-3-642-03685-9_20","volume-title":"APPROX\/RANDOM\u201909","author":"Magen Avner","year":"2009","unstructured":"Avner Magen and Mohammad Moharrami. 2009. Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy. In APPROX\/RANDOM\u201909(Lecture Notes in Computer Science, Vol. 5687). 258\u2013271."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90133-W"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_28_2","volume-title":"Treewidth-based Conditions for Exactness of the Sherali-Adams and Lasserre Relaxations","author":"Wainwright Martin J.","year":"2004","unstructured":"Martin J. Wainwright and Michael I. Jordan. 2004. Treewidth-based Conditions for Exactness of the Sherali-Adams and Lasserre Relaxations. Technical Report. Technical Report 671, University of California, Berkeley."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632623","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:57:54Z","timestamp":1750294674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,22]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3632623"],"URL":"https:\/\/doi.org\/10.1145\/3632623","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,1,22]]},"assertion":[{"value":"2021-09-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}