{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T23:24:31Z","timestamp":1767828271020,"version":"3.49.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["NK105 645"],"award-info":[{"award-number":["NK105 645"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001602","name":"Science Foundation Ireland","doi-asserted-by":"publisher","award":["10\/IN.1\/13032"],"award-info":[{"award-number":["10\/IN.1\/13032"]}],"id":[{"id":"10.13039\/501100001602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>\n            We present a method for reducing the treewidth of a graph while preserving all of its minimal\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            separators up to a certain fixed size\n            <jats:italic>k<\/jats:italic>\n            . This technique allows us to solve\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            <jats:sc>Cut<\/jats:sc>\n            and\n            <jats:sc>Multicut<\/jats:sc>\n            problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number\n            <jats:italic>k<\/jats:italic>\n            of removed vertices.\n          <\/jats:p>\n          <jats:p>\n            Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. For example, we can solve similarly restricted generalizations of\n            <jats:sc>Bipartization<\/jats:sc>\n            (delete at most\n            <jats:italic>k<\/jats:italic>\n            vertices from\n            <jats:italic>G<\/jats:italic>\n            to make it bipartite) in almost linear time for every fixed number\n            <jats:italic>k<\/jats:italic>\n            of removed vertices. These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for (\n            <jats:italic>H<\/jats:italic>\n            ,\n            <jats:italic>C<\/jats:italic>\n            ,\n            <jats:italic>K<\/jats:italic>\n            )- and (\n            <jats:italic>H<\/jats:italic>\n            ,\n            <jats:italic>C<\/jats:italic>\n            ,\u2264K)-coloring problems as well, which are cardinality constrained variants of the classical\n            <jats:italic>H<\/jats:italic>\n            -coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound.\n          <\/jats:p>","DOI":"10.1145\/2500119","type":"journal-article","created":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T18:14:28Z","timestamp":1380651268000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":69,"title":["Finding small separators in linear time via treewidth reduction"],"prefix":"10.1145","volume":"9","author":[{"given":"D\u00e1aniel","family":"Marx","sequence":"first","affiliation":[{"name":"Hungarian Academy of Sciences (MTA SZTAKI)"}]},{"given":"Barry","family":"O'sullivan","sequence":"additional","affiliation":[{"name":"University College Cork, Ireland"}]},{"given":"Igor","family":"Razgon","sequence":"additional","affiliation":[{"name":"University of Leicester"}]}],"member":"320","published-online":{"date-parts":[[2013,10,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_13"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008967.2009036"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.12.016"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993698"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00223-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.011"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of WADS. 495--506","author":"Chen J."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_13_1","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28050-4_1"},{"key":"e_1_2_1_15_1","volume-title":"Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings.","author":"Demaine E."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.008"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"D\u00edaz J. Serna M. and \n      \n      \n      Thilikos D. M\n      \n  \n  . \n  2001\n  . (H C K)-coloring: Fast easy and hard cases. In Mathematical Foundations of Computer Science (Mari\u00e1nsk\u00e9 L\u00e1zn\u0115) Lecture Notes in Computer Science Series vol. \n  2136 Springer Berlin 304--315.   D\u00edaz J. Serna M. and Thilikos D. M. 2001. (H C K)-coloring: Fast easy and hard cases. In Mathematical Foundations of Computer Science (Mari\u00e1nsk\u00e9 L\u00e1zn\u0115) Lecture Notes in Computer Science Series vol. 2136 Springer Berlin 304--315.","DOI":"10.1007\/3-540-44683-4_27"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.018"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.058"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.02.004"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Monographs in Computer Science Springer New York.   Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Monographs in Computer Science Springer New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103422184"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132573"},{"key":"e_1_2_1_26_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00009-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28050-4_6"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.03.005"},{"key":"e_1_2_1_30_1","unstructured":"Grohe M. 2007. Logic graphs and algorithms. In Logic and Automata- History and Perspectives J. Flum E. Gr\u00e4del and T. Wilke Eds. Amsterdam University Press.  Grohe M. 2007. Logic graphs and algorithms. In Logic and Automata- History and Perspectives J. Flum E. Gr\u00e4del and T. Wilke Eds. Amsterdam University Press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.02.014"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of LATIN. 182--193","author":"Gupta A."},{"key":"e_1_2_1_35_1","unstructured":"Gutin G. Hell P. Rafiey A. and Yeo A. 2006. Minimum cost homomorphisms to proper interval graphs and bigraphs. CoRR abs\/cs\/0602038.  Gutin G. Hell P. Rafiey A. and Yeo A. 2006. Minimum cost homomorphisms to proper interval graphs and bigraphs. CoRR abs\/cs\/0602038."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.012"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28050-4_5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2011.05.016"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of FSTTCS. 217--228","author":"Heggernes P."},{"key":"e_1_2_1_40_1","volume-title":"Topics in Discrete Mathematics, Algorithms Combin. Series","author":"Hell P."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9150-x"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of ESA. 122--133","author":"Kaminski M."},{"key":"e_1_2_1_44_1","unstructured":"Kanj I. 2008. Open problem session of Dagstuhl seminar 08431.  Kanj I. 2008. Open problem session of Dagstuhl seminar 08431."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10)","author":"Kawarabayashi K."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208049"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789708"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10217-2_37"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of STACS. 561--572","author":"Marx D."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.07.016"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993699"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_59"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and cits Applications Series vol. 31 Oxford University Press Oxford UK.  Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and cits Applications Series vol. 31 Oxford University Press Oxford UK.","DOI":"10.1093\/acprof:oso\/9780198566076.003.0001"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120902"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_60_1","volume-title":"Surveys in Combinatorics","author":"Reed B."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_62_1","unstructured":"Samer M. and Szeider S. 2006. Complexity and applications of edge-induced vertex-cuts. CoRR abs\/cs\/0607109.  Samer M. and Szeider S. 2006. Complexity and applications of edge-induced vertex-cuts. CoRR abs\/cs\/0607109."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm038"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11266-9_42"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9215-5"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210021"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500119","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2500119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:31Z","timestamp":1750232071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":67,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1145\/2500119"],"URL":"https:\/\/doi.org\/10.1145\/2500119","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}