{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:52:01Z","timestamp":1725688321344},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_32","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T22:21:27Z","timestamp":1339539687000},"page":"364-375","source":"Crossref","is-referenced-by-count":8,"title":["Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"8","key":"32_CR1","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences\u00a075(8), 423\u2013434 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR2","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: STACS, pp. 165\u2013176 (2011)"},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: SODA, pp. 68\u201381 (2012)","DOI":"10.1137\/1.9781611973099.6"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251\u2013260 (2010)","DOI":"10.1145\/1806689.1806725"},{"key":"32_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through Colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L. Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences\u00a077, 91\u2013106 (2011)","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: SODA, pp. 104\u2013113 (2012)","DOI":"10.1137\/1.9781611973099.9"},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Kratsch, S.: Co-nondeterminism in compositions: a kernelization lower bound for a ramsey-type problem. In: SODA, pp. 114\u2013122 (2012)","DOI":"10.1137\/1.9781611973099.10"},{"issue":"5","key":"32_CR9","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/060668092","volume":"39","author":"D. Harnik","year":"2010","unstructured":"Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. SIAM Journal on Computing\u00a039(5), 1667\u20131713 (2010)","journal-title":"SIAM Journal on Computing"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S. Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science\u00a0289, 997\u20131008 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"32_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences\u00a020(2), 219\u2013230 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR12","first-page":"463","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica\u00a02, 463\u2013470 (1935)","journal-title":"Compositio Mathematica"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P. Erd\u0151s","year":"1947","unstructured":"Erd\u0151s, P.: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society\u00a053, 292\u2013294 (1947)","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"1-2","key":"32_CR14","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(89)90045-0","volume":"25","author":"P. Erd\u0151s","year":"1989","unstructured":"Erd\u0151s, P., Hajnal, A.: Ramsey-type theorems. Discrete Applied Mathematics\u00a025(1-2), 37\u201352 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters\u00a058, 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"issue":"4","key":"32_CR16","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D. Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica\u00a057(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"issue":"3-4","key":"32_CR17","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1007\/s00453-010-9484-z","volume":"62","author":"D. Marx","year":"2012","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica\u00a062(3-4), 807\u2013822 (2012)","journal-title":"Algorithmica"},{"key":"32_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/978-3-642-16926-7_22","volume-title":"Graph Theoretic Concepts in Computer Science","author":"R. Bevern van","year":"2010","unstructured":"van Bevern, R., Komusiewicz, C., Moser, H., Niedermeier, R.: Measuring Indifference: Unit Interval Vertex Deletion. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 232\u2013243. Springer, Heidelberg (2010)"},{"key":"32_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-17493-3_22","volume-title":"Parameterized and Exact Computation","author":"Y. Villanger","year":"2010","unstructured":"Villanger, Y.: Proper Interval Vertex Deletion. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 228\u2013238. Springer, Heidelberg (2010)"},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory. Springer (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Elsevier Science (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"issue":"2","key":"32_CR22","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s004930100016","volume":"21","author":"N. Alon","year":"2001","unstructured":"Alon, N., Pach, J., Solymosi, J.: Ramsey-type theorems with forbidden subgraphs. Combinatorica\u00a021(2), 155\u2013170 (2001)","journal-title":"Combinatorica"},{"key":"32_CR23","first-page":"55","volume-title":"Selected Topics in Graph Theory","author":"L. Lovasz","year":"1983","unstructured":"Lovasz, L.: Perfect graphs. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, vol.\u00a02, pp. 55\u201367. Academic Press, London (1983)"},{"issue":"35","key":"32_CR24","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science\u00a0412(35), 4570\u20134578 (2011)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:48:38Z","timestamp":1620114518000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}