{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T21:31:34Z","timestamp":1773091894329,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["677651, 714704, 715744, and 819416"],"award-info":[{"award-number":["677651, 714704, 715744, and 819416"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2018302"],"award-info":[{"award-number":["2018302"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2015\/19\/N\/ST6\/03015"],"award-info":[{"award-number":["UMO-2015\/19\/N\/ST6\/03015"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA01\/2017-18"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>\n            We show an algorithm that, given an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            and a parameter\n            <jats:italic>k<\/jats:italic>\n            , in time 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              log\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            finds a tree decomposition of\n            <jats:italic>G<\/jats:italic>\n            with the following properties:\n          <\/jats:p>\n          <jats:p>\n            \u2014 every adhesion of the tree decomposition is of size at most\n            <jats:italic>k<\/jats:italic>\n            , and\n          <\/jats:p>\n          <jats:p>\n            \u2014 every bag of the tree decomposition is (\n            <jats:italic>i<\/jats:italic>\n            ,\n            <jats:italic>i<\/jats:italic>\n            )-unbreakable in\n            <jats:italic>G<\/jats:italic>\n            for every 1 \u2a7d\n            <jats:italic>i<\/jats:italic>\n            \u2a7d\n            <jats:italic>k<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Here, a set\n            <jats:italic>X<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) is (\n            <jats:italic>a<\/jats:italic>\n            ,\n            <jats:italic>b<\/jats:italic>\n            )-unbreakable in\n            <jats:italic>G<\/jats:italic>\n            if for every separation (\n            <jats:italic>A<\/jats:italic>\n            ,\n            <jats:italic>B<\/jats:italic>\n            ) of order at most\n            <jats:italic>b<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            , we have |\n            <jats:italic>A<\/jats:italic>\n            \\cap\n            <jats:italic>X<\/jats:italic>\n            | \u2a7d\n            <jats:italic>a<\/jats:italic>\n            or |\n            <jats:italic>B<\/jats:italic>\n            \u2229\n            <jats:italic>X<\/jats:italic>\n            | \u2a7d\n            <jats:italic>a<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            The resulting tree decomposition has arguably best possible adhesion size bounds and unbreakability guarantees. Furthermore, the parametric factor in the running time bound is significantly smaller than in previous similar constructions. These improvements allow us to present parameterized algorithms for M\n            <jats:sc>INIMUM<\/jats:sc>\n            B\n            <jats:sc>ISECTION<\/jats:sc>\n            , S\n            <jats:sc>TEINER<\/jats:sc>\n            C\n            <jats:sc>UT<\/jats:sc>\n            , and S\n            <jats:sc>TEINER<\/jats:sc>\n            M\n            <jats:sc>ULTICUT<\/jats:sc>\n            with improved parameteric factor in the running time bound.\n          <\/jats:p>\n          <jats:p>\n            The main technical insight is to adapt the notion of\n            <jats:italic>lean decompositions<\/jats:italic>\n            of Thomas and the subsequent construction algorithm of Bellenbaum and Diestel to the parameterized setting.\n          <\/jats:p>","DOI":"10.1145\/3426738","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T18:48:01Z","timestamp":1609440481000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Randomized Contractions Meet Lean Decompositions"],"prefix":"10.1145","volume":"17","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Komosa","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen and Institute of Mathematical Sciences, Tharamani, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham Hill, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005369"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934508"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.03.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032077"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.29"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086217X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591852"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2900728.2900798"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.003"},{"key":"e_1_2_1_14_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","volume":"80","author":"Iwata Yoichi","year":"2017","unstructured":"Yoichi Iwata . 2017 . Linear-time kernelization for feedback vertex set. In 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) (LIPIcs), Vol. 80 . Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 68:1--68:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2017.68 10.4230\/LIPIcs.ICALP.2017.68 Yoichi Iwata. 2017. Linear-time kernelization for feedback vertex set. In 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) (LIPIcs), Vol. 80. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 68:1--68:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.68"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/140962838"},{"key":"e_1_2_1_16_1","volume-title":"Linear-time FPT algorithms via half-integral non-returning A-path packing. CoRR abs\/1704.02700","author":"Iwata Yoichi","year":"2017","unstructured":"Yoichi Iwata , Yutaro Yamaguchi , and Yuichi Yoshida . 2017. Linear-time FPT algorithms via half-integral non-returning A-path packing. CoRR abs\/1704.02700 ( 2017 ). arxiv:1704.02700 http:\/\/arxiv.org\/abs\/1704.02700 Yoichi Iwata, Yutaro Yamaguchi, and Yuichi Yoshida. 2017. Linear-time FPT algorithms via half-integral non-returning A-path packing. CoRR abs\/1704.02700 (2017). arxiv:1704.02700 http:\/\/arxiv.org\/abs\/1704.02700"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.53"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.016"},{"key":"e_1_2_1_21_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","volume":"107","author":"Lokshtanov Daniel","year":"2018","unstructured":"Daniel Lokshtanov , M. S. Ramanujan , Saket Saurabh , and Meirav Zehavi . 2018 . Reducing CMSO model checking to highly connected graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) (LIPIcs), Vol. 107 . Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 135:1--135:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2018.135 10.4230\/LIPIcs.ICALP.2018.135 Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. 2018. Reducing CMSO model checking to highly connected graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) (LIPIcs), Vol. 107. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, 135:1--135:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.135"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500119"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90130-R"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426738","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3426738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:45Z","timestamp":1750197705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3426738"],"URL":"https:\/\/doi.org\/10.1145\/3426738","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,31]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}