{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T20:48:37Z","timestamp":1777668517501,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,9,16]],"date-time":"2014-09-16T00:00:00Z","timestamp":1410825600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s00453-014-9937-x","type":"journal-article","created":{"date-parts":[[2014,9,15]],"date-time":"2014-09-15T17:49:05Z","timestamp":1410803345000},"page":"731-757","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Incompressibility of $$H$$ H -Free Edge Modification Problems"],"prefix":"10.1007","volume":"71","author":[{"given":"Leizhen","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yufei","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,16]]},"reference":[{"key":"9937_CR1","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Cai, L., Chen, J., Fellows, M.R., Telle, J.A., Marx, D.: Open Problems in Parameterized and Exact Computation\u2014IWPEC 2006. Utrecht University Technical Report UU-CS-2006-052 (2006)","DOI":"10.1007\/11847250"},{"issue":"8","key":"9937_CR2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9937_CR3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B., Kratsch, S.: Kernelization lower bounds by cross-compositions. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"35","key":"9937_CR4","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9937_CR5","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0020-0190(96)00056-7","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 157\u2013206 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9937_CR6","doi-asserted-by":"crossref","unstructured":"Cai, L., Cai, Y.: Incompressibility of $$H$$ H -free edge modification. In: Gutin, G., Szeider, S. (eds.) 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), Lecture Notes in Computer Science, vol. 8246, pp. 84\u201396 (2013)","DOI":"10.1007\/978-3-319-03898-8_9"},{"key":"9937_CR7","unstructured":"Cai, Y.: Polynomial Kernelisation of $$H$$ H -free Edge Modification Problems, MPhil Thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong SAR, China (2012). http:\/\/www.uni-marburg.de\/fb12\/ps\/team\/cai-masterarbeit.pdf"},{"issue":"1","key":"9937_CR8","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9937_CR9","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: fixed parameter algorithms for clique generation. Theory Comput. Syst. 38(4), 373\u2013392 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"9937_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"9937_CR11","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Paul, C., Perez, A.: P On the (non-)existence of polynomial kernels for $$P_l$$ P l -free edge modification problems. In: Raman, V., Saurabh, S. (eds.), 5th International Symposium on Parameterized and Exact Computation (IPEC 2010), Lecture Notes in Computer Science, vol. 6478, pp. 147\u2013157 (2010)","DOI":"10.1007\/978-3-642-17493-3_15"},{"issue":"4","key":"9937_CR12","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1007\/s00453-012-9619-5","volume":"65","author":"S Guillemot","year":"2013","unstructured":"Guillemot, S., Havet, F., Paul, C., Perez, A.: On the (non-)existence of polynomial kernels for $$P_l$$ P l -free edge modification problems. Algorithmica 65(4), 900\u2013926 (2013)","journal-title":"Algorithmica"},{"key":"9937_CR13","doi-asserted-by":"crossref","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Tokuyama, T. (ed.), 18th International Symposium on Algorithms and Complexity (ISAAC 2007), Lecture Notes in Computer Science, vol. 4835, pp. 915\u2013926 (2007)","DOI":"10.1007\/978-3-540-77120-3_79"},{"key":"9937_CR14","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.disopt.2013.02.001","volume":"10","author":"S Kratsch","year":"2013","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. Discrete Optim. 10, 193\u2013199 (2013)","journal-title":"Discrete Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9937-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9937-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9937-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,15]],"date-time":"2019-08-15T00:30:57Z","timestamp":1565829057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9937-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,16]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["9937"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9937-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,16]]}}}