{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T20:39:56Z","timestamp":1772829596083,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:00:00Z","timestamp":1559260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["PARAPPROX, Reference No. 306992"],"award-info":[{"award-number":["PARAPPROX, Reference No. 306992"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this article, we examine an important family of graphs, namely, the family of split graphs, which in the context of edge contractions is proven to be significantly less obedient than one might expect. Formally, given a graph\n            <jats:italic>G<\/jats:italic>\n            and an integer\n            <jats:italic>k<\/jats:italic>\n            , S\n            <jats:sc>PLIT<\/jats:sc>\n            C\n            <jats:sc>ONTRACTION<\/jats:sc>\n            asks whether there exists\n            <jats:italic>X<\/jats:italic>\n            \u2286\n            <jats:italic>E<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) such that\n            <jats:italic>G<\/jats:italic>\n            \/\n            <jats:italic>X<\/jats:italic>\n            is a split graph and |\n            <jats:italic>X<\/jats:italic>\n            | \u2264\n            <jats:italic>k<\/jats:italic>\n            . Here,\n            <jats:italic>G<\/jats:italic>\n            \/\n            <jats:italic>X<\/jats:italic>\n            is the graph obtained from\n            <jats:italic>G<\/jats:italic>\n            by contracting edges in\n            <jats:italic>X<\/jats:italic>\n            . Guo and Cai [Theoretical Computer Science, 2015] claimed that S\n            <jats:sc>PLIT<\/jats:sc>\n            C\n            <jats:sc>ONTRACTION<\/jats:sc>\n            is fixed-parameter tractable. However, our findings are different. We show that S\n            <jats:sc>PLIT<\/jats:sc>\n            C\n            <jats:sc>ONTRACTION<\/jats:sc>\n            , despite its deceptive simplicity, is W[1]-hard. Our main result establishes the following conditional lower bound: Under the Exponential Time Hypothesis, S\n            <jats:sc>PLIT<\/jats:sc>\n            C\n            <jats:sc>ONTRACTION<\/jats:sc>\n            cannot be solved in time 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n            <\/jats:sup>\n            (\u2113\n            <jats:sup>2<\/jats:sup>\n            )\u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>O<\/jats:sup>\n            (1), where \u2113 is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the\n            <jats:italic>first<\/jats:italic>\n            tight lower bound of the form 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n            <\/jats:sup>\n            (\u2113\n            <jats:sup>2<\/jats:sup>\n            )\u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/3319909","type":"journal-article","created":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T12:23:16Z","timestamp":1559564596000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Split Contraction"],"prefix":"10.1145","volume":"11","author":[{"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Science, HBNI, India and Department of Informatics, University of Bergen, Norway and UMI ReLax"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,5,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90012-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884514"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/140988565"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186896"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_10"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884512"},{"key":"e_1_2_1_8_1","first-page":"109","article-title":"Unit interval editing is fixed-parameter tractable. Info","volume":"253","author":"Cao Yixin","year":"2017","unstructured":"Yixin Cao . 2017 . Unit interval editing is fixed-parameter tractable. Info . Comput. 253 (2017), 109 -- 126 . Yixin Cao. 2017. Unit interval editing is fixed-parameter tractable. Info. Comput. 253 (2017), 109--126.","journal-title":"Comput."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629595"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0014-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051094"},{"key":"e_1_2_1_13_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141ukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer International Publishing , Switzerland . Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer International Publishing, Switzerland."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/130947076"},{"key":"e_1_2_1_15_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2012. Graph Theory , 4 th ed. Graduate texts in mathematics, Vol. 173 . Springer-Verlag , Berlin. Reinhard Diestel. 2012. Graph Theory, 4th ed. Graduate texts in mathematics, Vol. 173. Springer-Verlag, Berlin.","edition":"4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_17_1","volume-title":"Fellows","author":"Downey Rod G.","year":"2013","unstructured":"Rod G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer-Verlag , London. Rod G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer-Verlag, London."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915)","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange , Markus Sortland Dregi , Daniel Lokshtanov , and Blair D. Sullivan . 2015. On the threshold of intractability . In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915) . Springer-Verlag, Berlin, 411--423. P\u00e5l Gr\u00f8n\u00e5s Drange, Markus Sortland Dregi, Daniel Lokshtanov, and Blair D. Sullivan. 2015. On the threshold of intractability. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915). Springer-Verlag, Berlin, 411--423."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2799640"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3288645.3288672"},{"key":"e_1_2_1_21_1","volume-title":"Surveys in Combinatorics","author":"Edwards Keith","unstructured":"Keith Edwards . 1997. The harmonious chromatic number and the achromatic number . In Surveys in Combinatorics . Cambridge University Press , Cambridge , 13--48. Keith Edwards. 1997. The harmonious chromatic number and the achromatic number. In Surveys in Combinatorics. Cambridge University Press, Cambridge, 13--48."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_2_1_23_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , Berlin . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.04.015"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085390X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9837-5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.041"},{"key":"e_1_2_1_28_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","unstructured":"Martin Charles Golumbic . 2004. Algorithmic Graph Theory and Perfect Graphs . Vol. 57 . Elsevier , Academic Press . Martin Charles Golumbic. 2004. Algorithmic Graph Theory and Perfect Graphs. Vol. 57. Elsevier, Academic Press."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.004"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.01.056"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9670-2"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/130907392"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303044"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186589"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110414"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104834"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_21"},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, (ICALP\u201916). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl","volume":"28","author":"Marx D\u00e1niel","year":"2016","unstructured":"D\u00e1niel Marx and Valia Mitsou . 2016 . Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, (ICALP\u201916). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl , Germany , 28 : 1 -- 28 :15. D\u00e1niel Marx and Valia Mitsou. 2016. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, (ICALP\u201916). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 28:1--28:15.","journal-title":"Germany"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150606"},{"key":"e_1_2_1_41_1","volume-title":"Invitation to Fixed-parameter Algorithms","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-parameter Algorithms . Oxford University Press , Oxford . Rolf Niedermeier. 2006. Invitation to Fixed-parameter Algorithms. Oxford University Press, Oxford."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90022-9"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90039-1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90101-4"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319909","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3319909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:06Z","timestamp":1750208886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319909"}},"subtitle":["The Untold Story"],"short-title":[],"issued":{"date-parts":[[2019,5,31]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3319909"],"URL":"https:\/\/doi.org\/10.1145\/3319909","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,31]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}