{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:59:31Z","timestamp":1764784771267,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572414"],"award-info":[{"award-number":["61572414"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["15201317","15226116"],"award-info":[{"award-number":["15201317","15226116"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00453-021-00891-y","type":"journal-article","created":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T16:02:37Z","timestamp":1637424157000},"page":"197-215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Polynomial Kernel for Diamond-Free Editing"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6927-438X","authenticated-orcid":false,"given":"Yixin","family":"Cao","sequence":"first","affiliation":[]},{"given":"Ashutosh","family":"Rai","sequence":"additional","affiliation":[]},{"given":"R. B.","family":"Sandeep","sequence":"additional","affiliation":[]},{"given":"Junjie","family":"Ye","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"891_CR1","doi-asserted-by":"publisher","unstructured":"Abu-Khzam, Faisal\u00a0N.: A kernelization algorithm for $$d$$-hitting set. J. Comp. Syst. Sci. 76(7):524\u2013531, (2010). A preliminary version appeared in WADS 2007. https:\/\/doi.org\/10.1016\/j.jcss.2009.09.002","DOI":"10.1016\/j.jcss.2009.09.002"},{"issue":"1","key":"891_CR2","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1137\/16M1055797","volume":"31","author":"NR Aravind","year":"2017","unstructured":"Aravind, N.R., Sandeep, R.B., Sivadasan, N.: Dichotomy results on the hardness of $$H$$-free edge modification problems. SIAM J. Dis. Math. 31(1), 542\u2013561 (2017). https:\/\/doi.org\/10.1137\/16M1055797","journal-title":"SIAM J. Dis. Math."},{"key":"891_CR3","doi-asserted-by":"publisher","unstructured":"Bliznets, Ivan., Cygan, Marek., Komosa, Pawel., Pilipczuk, Micha\u0142.: Hardness of approximation for $$H$$-free edge modification problems. ACM Trans. Comput. Theory, 10(2):9:1\u20139:32, (2018). A preliminary version appeared in APPROX 2016. https:\/\/doi.org\/10.1145\/3196834","DOI":"10.1145\/3196834"},{"issue":"4","key":"891_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"Leizhen Cai","year":"1996","unstructured":"Cai, Leizhen: Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Process. Lett. 58(4), 171\u2013176 (1996). https:\/\/doi.org\/10.1016\/0020-0190(96)00050-6","journal-title":"Inform. Process. Lett."},{"key":"891_CR5","doi-asserted-by":"publisher","unstructured":"Cai, Leizhen., Cai, Yufei.: Incompressibility of $$H$$-free edge modification problems. Algorithmica, 71(3):731\u2013757, (2015). A preliminary version appeared in IPEC 2013. https:\/\/doi.org\/10.1007\/s00453-014-9937-x","DOI":"10.1007\/s00453-014-9937-x"},{"key":"891_CR6","doi-asserted-by":"publisher","unstructured":"Cao, Yixin., Chen, Jianer.: Cluster editing: Kernelization based on edge cuts. Algorithmica, 64(1):152\u2013169, (2012). A preliminary version appeared in IPEC 2010. https:\/\/doi.org\/10.1007\/s00453-011-9595-1","DOI":"10.1007\/s00453-011-9595-1"},{"key":"891_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","author":"Rodney G Downey","year":"2013","unstructured":"Downey, Rodney G., Fellows, Michael R.: Fundamentals of Parameterized Complexity. Undergraduate Texts Comp. Sci. (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","journal-title":"Undergraduate Texts Comp. Sci."},{"key":"891_CR8","doi-asserted-by":"publisher","unstructured":"Eiben, Eduard: Lochet, William, Saurabh, Saket: A polynomial kernel for paw-free editing. Presented at the (2020). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.10","DOI":"10.4230\/LIPIcs.IPEC.2020.10"},{"issue":"3","key":"891_CR9","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"Ehab S El-Mallah","year":"1988","unstructured":"El-Mallah, Ehab S., Colbourn, Charles J.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst. 35(3), 354\u2013362 (1988). https:\/\/doi.org\/10.1109\/31.1748","journal-title":"IEEE Trans. Circuits Syst."},{"issue":"1","key":"891_CR10","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Rado, R.: Intersection theorems for systems of sets. J. London Math. Soc. 35(1), 85\u201390 (1960). https:\/\/doi.org\/10.1112\/jlms\/s1-35.1.85","journal-title":"J. London Math. Soc."},{"key":"891_CR11","volume-title":"Parameterized Complexity Theory","author":"J\u00f6rg Flum","year":"2006","unstructured":"Flum, J\u00f6rg., Grohe, Martin: Parameterized Complexity Theory. Springer, Ny (2006)"},{"key":"891_CR12","doi-asserted-by":"publisher","unstructured":"Guillemot, Sylvain., Havet, Fr\u00e9d\u00e9ric., Paul, Christophe., Perez, Anthony.: On the (non-)existence of polynomial kernels for $$P_l$$ -free edge modification problems. Algorithmica, 65(4):900\u2013926, (2013). A preliminary version with weaker results appeared in IPEC 2010. https:\/\/doi.org\/10.1007\/s00453-012-9619-5","DOI":"10.1007\/s00453-012-9619-5"},{"key":"891_CR13","doi-asserted-by":"publisher","unstructured":"Impagliazzo, Russell., Paturi, Ramamohan.: On the complexity of $$k$$-SAT. J. Comp. Syst. Sci., 62(2):367\u2013375, (2001). A preliminary version appeared in CCC 1999. https:\/\/doi.org\/10.1006\/jcss.2000.1727","DOI":"10.1006\/jcss.2000.1727"},{"key":"891_CR14","doi-asserted-by":"publisher","unstructured":"Kratsch, Stefan., Wahlstr\u00f6m, Magnus.: Two edge modification problems without polynomial kernels. Dis. Optim., 10(3):193\u2013199, (2013). A preliminary version appeared in IWPEC 2009. https:\/\/doi.org\/10.1016\/j.disopt.2013.02.001","DOI":"10.1016\/j.disopt.2013.02.001"},{"key":"891_CR15","doi-asserted-by":"publisher","unstructured":"Lewis, John\u00a0M., Yannakakis, Mihalis.: The node-deletion problem for hereditary properties is NP-complete. J. Comp. Syst. Sci., 20(2):219\u2013230, (1980). Preliminary versions independently presented in STOC 1978. https:\/\/doi.org\/10.1016\/0022-0000(80)90060-4","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"891_CR16","doi-asserted-by":"publisher","unstructured":"Sandeep, R.B., Sivadasan, Naveen: In: Husfeldt, Thore, Kanj, Iyad A. (eds.) Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, pp. 365\u2013376. (2015). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2015.365","DOI":"10.4230\/LIPIcs.IPEC.2015.365"},{"issue":"2","key":"891_CR17","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"Mihalis Yannakakis","year":"1981","unstructured":"Yannakakis, Mihalis: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981). https:\/\/doi.org\/10.1137\/0210022","journal-title":"SIAM J. Comput."},{"key":"891_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2021.08.015","volume":"891","author":"H Yuan","year":"2021","unstructured":"Yuan, H., Ke, Y., Cao, Y.: Polynomial kernels for paw-free edge modification problems. Theor. Comp. Sci. 891, 1\u201312 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.08.015","journal-title":"Theor. Comp. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00891-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00891-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00891-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:08:25Z","timestamp":1643033305000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00891-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["891"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00891-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,11,20]]},"assertion":[{"value":"11 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}