{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:31Z","timestamp":1759638931575,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T00:00:00Z","timestamp":1421107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001502","name":"Department of Atomic Energy, Government of India","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["N206567140"],"award-info":[{"award-number":["N206567140"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"DOI":"10.13039\/501100001870","name":"Foundation For Polish Science","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001870","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":[[2015,1,13]]},"abstract":"<jats:p>\n            This work further explores the applications of co-nondeterminism for showing kernelization lower bounds. The only known example prior to this work excludes polynomial kernelizations for the so-called Ramsey problem of finding an independent set or a clique of at least\n            <jats:italic>k<\/jats:italic>\n            vertices in a given graph [Kratsch 2012]. We study the more general problem of finding induced subgraphs on\n            <jats:italic>k<\/jats:italic>\n            vertices fulfilling some hereditary property \u03a0, called \u03a0-Induced Subgraph. The problem is NP-hard for all nontrivial choices of \u03a0 by a classic result of Lewis and Yannakakis [1980]. The parameterized complexity of this problem was classified by Khot and Raman [2002] depending on the choice of \u03a0. The interesting cases for kernelization are for \u03a0 containing all independent sets and all cliques, since the problem is trivially polynomial time solvable or W[1]-hard otherwise.\n          <\/jats:p>\n          <jats:p>\n            Our results are twofold. Regarding \u03a0-Induced Subgraph, we show that for a large choice of natural graph properties \u03a0, including chordal, perfect, cluster, and cograph, there is no polynomial kernel with respect to\n            <jats:italic>k<\/jats:italic>\n            . This is established by two theorems, each one capturing different (but not necessarily exclusive) sets of properties: one using a co-nondeterministic variant of OR-cross-composition and one by a polynomial parameter transformation from Ramsey.\n          <\/jats:p>\n          <jats:p>\n            Additionally, we show how to use improvement versions of NP-hard problems as source problems for lower bounds, without requiring their NP-hardness. For example, for \u03a0-Induced Subgraph our compositions may assume existing solutions of size k--1. This follows from the more general fact that source problems for OR-(cross-)compositions need only be NP-hard under\n            <jats:italic>co-nondeterministic<\/jats:italic>\n            reductions. We believe this to be useful for further lower-bound proofs, for example, since improvement versions simplify the construction of a disjunction (OR) of instances required in compositions. This adds a second way of using co-nondeterminism for lower bounds.\n          <\/jats:p>","DOI":"10.1145\/2691321","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T14:29:58Z","timestamp":1421418598000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs"],"prefix":"10.1145","volume":"7","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[{"name":"Utrecht University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930100016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/120880240"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"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.5555\/2095116.2095122"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"volume-title":"Graph Theory","author":"Diestel Reinhard","key":"e_1_2_1_8_1","unstructured":"Reinhard Diestel . 2005. Graph Theory . Springer . Reinhard Diestel. 2005. Graph Theory. Springer."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90045-0"},{"key":"e_1_2_1_12_1","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s Paul","year":"1935","unstructured":"Paul Erd\u0151s and George Szekeres . 1935 . A combinatorial problem in geometry . Compositio Mathematica 2 , 463 -- 470 . Paul Erd\u0151s and George Szekeres. 1935. A combinatorial problem in geometry. Compositio Mathematica 2, 463--470.","journal-title":"Compositio Mathematica"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/12089051X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_15_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin C.","unstructured":"Martin C. Golumbic . 2004. Algorithmic Graph Theory and Perfect Graphs , 2 nd Ed. Elsevier Science . Martin C. Golumbic. 2004. Algorithmic Graph Theory and Perfect Graphs, 2nd Ed. Elsevier Science.","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095125"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00414-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095126"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_32"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_22_1","first-page":"L","article-title":"Perfect graphs","volume":"2","author":"Lovasz L\u00e1szl\u00f3","year":"1983","unstructured":"L\u00e1szl\u00f3 Lovasz . 1983 . Perfect graphs . In Selected Topics in Graph Theory , Volume 2 , L . W. Beineke and R. J. Wilson (Eds.), Academic Press, London-New York, 55--67. L\u00e1szl\u00f3 Lovasz. 1983. Perfect graphs. In Selected Topics in Graph Theory, Volume 2, L. W. Beineke and R. J. Wilson (Eds.), Academic Press, London-New York, 55--67.","journal-title":"Selected Topics in Graph Theory"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9484-z"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1939238.1939262"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9661-3"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2691321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2691321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:08Z","timestamp":1750227128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2691321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,13]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1,13]]}},"alternative-id":["10.1145\/2691321"],"URL":"https:\/\/doi.org\/10.1145\/2691321","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2015,1,13]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}