{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T16:54:29Z","timestamp":1771779269674,"version":"3.50.1"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"name":"KERNELS"},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC 267959"],"award-info":[{"award-number":["ERC 267959"]}],"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. Comput. Theory"],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the polynomial hierarchy collapses to its third level, the following parameterized problems do not admit a polynomial-time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter:<\/jats:p>\n          <jats:p>\n            ---Edge Clique Cover, parameterized by the number of cliques, ---Directed Edge\/Vertex Multiway Cut, parameterized by the size of the cutset, even in the case of two terminals, ---Edge\/Vertex Multicut, parameterized by the size of the cutset, and ---\n            <jats:italic>k<\/jats:italic>\n            -Way Cut, parameterized by the size of the cutset.\n          <\/jats:p>","DOI":"10.1145\/2594439","type":"journal-article","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T12:50:17Z","timestamp":1402404617000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Clique Cover and Graph Separation"],"prefix":"10.1145","volume":"6","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"University of Warsaw"}]},{"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[{"name":"Utrecht University"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Bergen"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Max-Planck-Institute for Informatics"}]}],"member":"320","published-online":{"date-parts":[[2014,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574385"},{"key":"e_1_2_1_2_1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"Ausiello Giorgio","unstructured":"Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi , Viggo Kann , Alberto Marchetti-Spaccamela , and Marco Protasi . 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties . Springer . Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, and Marco Protasi. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.005"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/120903518"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/120880240"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993698"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00043-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.01.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of WG","author":"Chang Maw-Shang","unstructured":"Maw-Shang Chang and Haiko M\u00fcller . 2001. On the tree-degree of graphs . In Proceedings of WG . Lecture Notes in Computer Science , vol. 2204 , Springer , 44--54. Maw-Shang Chang and Haiko M\u00fcller. 2001. On the tree-degree of graphs. In Proceedings of WG. Lecture Notes in Computer Science, vol. 2204, Springer, 44--54."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086217X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.016"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843071"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095122"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)81014-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.71"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-014-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_28_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman , New York. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00111-1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.1.24"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412236"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2006.09.035"},{"key":"e_1_2_1_34_1","volume-title":"Gross and Jay Yellen","author":"Jonathan","year":"2006","unstructured":"Jonathan L. Gross and Jay Yellen . 2006 . Graph Theory and its Applications. CRC Press . Jonathan L. Gross and Jay Yellen. 2006. Graph Theory and its Applications. CRC Press."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.03.007"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.003"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095125"},{"key":"e_1_2_1_40_1","first-page":"187","article-title":"Complexity of graph covering problems for graphs of low degree","volume":"11","author":"Hoover Douglas N.","year":"1992","unstructured":"Douglas N. Hoover . 1992 . Complexity of graph covering problems for graphs of low degree . J. Combinat. Math. Combinat. Comput. 11 , 187 -- 208 . Douglas N. Hoover. 1992. Complexity of graph covering problems for graphs of low degree. J. Combinat. Math. Combinat. Comput. 11, 187--208.","journal-title":"J. Combinat. Math. Combinat. Comput."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90165-E"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/050631616"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0086"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.53"},{"key":"e_1_2_1_46_1","first-page":"544","article-title":"Determination of keyword conflict","volume":"16","author":"Kellerman Eduardo","year":"1973","unstructured":"Eduardo Kellerman . 1973 . Determination of keyword conflict . IBM Tech. Disclos. Bull. 16 , 2, 544 -- 546 . Eduardo Kellerman. 1973. Determination of keyword conflict. IBM Tech. Disclos. Bull. 16, 2, 544--546.","journal-title":"IBM Tech. Disclos. Bull."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359346"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_49"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095124"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_51_1","series-title":"Lecture Notes in Computer Science","volume-title":"Kernelization -- Preprocessing with a guarantee","author":"Lokshtanov Daniel","unstructured":"Daniel Lokshtanov , Neeldhara Misra , and Saket Saurabh . 2012. Kernelization -- Preprocessing with a guarantee . In The Multivariate Algorithmic Revolution and Beyond, Hans Bodlaender, Rod Downey, Fedor Fomin, and D\u00e1niel Marx Eds., Lecture Notes in Computer Science , vol. 7370 . Springer Berlin , 129--161. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-30891-8_10. 10.1007\/978-3-642-30891-8_10 Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Kernelization -- Preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond, Hans Bodlaender, Rod Downey, Fedor Fomin, and D\u00e1niel Marx Eds., Lecture Notes in Computer Science, vol. 7370. Springer Berlin, 129--161. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-642-30891-8_10."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_53_1","first-page":"151","article-title":"Clique covering of chordal graphs","volume":"36","author":"Ma Shaohan","year":"1989","unstructured":"Shaohan Ma , Walter D. Wallis , and Julin Wu . 1989 . Clique covering of chordal graphs . Util. Math. 36 , 151 -- 152 . Shaohan Ma, Walter D. Wallis, and Julin Wu. 1989. Clique covering of chordal graphs. Util. Math. 36, 151--152.","journal-title":"Util. Math."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"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.1137\/S009753979732147X"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(77)90055-5"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1198\/1061860043515"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/354880.354902"},{"key":"e_1_2_1_60_1","unstructured":"Igor Razgon. 2010. Computing multiway cut within the given excess over the largest minimum isolating cut. CoRR abs\/1011.6267.  Igor Razgon. 2010. Computing multiway cut within the given excess over the largest minimum isolating cut. CoRR abs\/1011.6267."},{"key":"e_1_2_1_61_1","volume-title":"Large isolating cuts shrink the multiway cut. CoRR abs\/1104.5361","author":"Razgon Igor","year":"2011","unstructured":"Igor Razgon . 2011. Large isolating cuts shrink the multiway cut. CoRR abs\/1104.5361 ( 2011 ). Igor Razgon. 2011. Large isolating cuts shrink the multiway cut. CoRR abs\/1104.5361 (2011)."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90061-7"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374402"},{"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.1016\/0304-3975(83)90020-8"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594439","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2594439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:52Z","timestamp":1750230052000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2594439"}},"subtitle":["New Incompressibility Results"],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2594439"],"URL":"https:\/\/doi.org\/10.1145\/2594439","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2013-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}