{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T20:44:31Z","timestamp":1777668271790,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T00:00:00Z","timestamp":1474588800000},"content-version":"unspecified","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":[[2017,11]]},"DOI":"10.1007\/s00453-016-0215-y","type":"journal-article","created":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T09:01:58Z","timestamp":1474621318000},"page":"654-666","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Polynomial Kernelization of $$\\mathcal {H}$$ H -free Edge Deletion"],"prefix":"10.1007","volume":"79","author":[{"given":"N. R.","family":"Aravind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. B.","family":"Sandeep","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naveen","family":"Sivadasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,23]]},"reference":[{"key":"215_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Shapira, A., Sudakov, B.: Additive approximation for edge-deletion problems. Ann. Math. 170(1), 371\u2013411 (2009)","DOI":"10.4007\/annals.2009.170.371"},{"key":"215_CR2","doi-asserted-by":"crossref","unstructured":"Aravind, N.R., Sandeep, R.B., Sivadasan, N.: Parameterized lower bounds and dichotomy results for the NP-completeness of H-free edge modification problems. In: LATIN 2016: Theoretical Informatics \u201412th Latin American Symposium, pp. 82\u201395 (2016)","DOI":"10.1007\/978-3-662-49529-2_7"},{"key":"215_CR3","doi-asserted-by":"crossref","unstructured":"Asano, T., Hirata, T.: Edge-deletion and edge-contraction problems. In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 245\u2013254. ACM (1982)","DOI":"10.1145\/800070.802198"},{"issue":"2","key":"215_CR4","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"LW Beineke","year":"1970","unstructured":"Beineke, L.W.: Characterizations of derived graphs. J. Comb. Theory 9(2), 129\u2013135 (1970)","journal-title":"J. Comb. Theory"},{"key":"215_CR5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.endm.2009.02.008","volume":"32","author":"D Br\u00fcgmann","year":"2009","unstructured":"Br\u00fcgmann, D., Komusiewicz, C., Moser, H.: On generating triangle-free graphs. Electron. Notes Discrete Math. 32, 51\u201358 (2009)","journal-title":"Electron. Notes Discrete Math."},{"issue":"13","key":"215_CR6","doi-asserted-by":"crossref","first-page":"1824","DOI":"10.1016\/j.dam.2006.03.031","volume":"154","author":"P Burzyn","year":"2006","unstructured":"Burzyn, P., Bonomo, F., Dur\u00e1n, G.: NP-completeness results for edge modification problems. Discrete Appl. Math. 154(13), 1824\u20131844 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"215_CR7","doi-asserted-by":"crossref","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. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"215_CR8","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1007\/s00453-014-9937-x","volume":"71","author":"L Cai","year":"2015","unstructured":"Cai, L., Cai, Y.: Incompressibility of H-free edge modification problems. Algorithmica 71(3), 731\u2013757 (2015)","journal-title":"Algorithmica"},{"key":"215_CR9","unstructured":"Cai, Y.: Polynomial kernelisation of H-free edge modification problems. Mphil Thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong SAR (2012)"},{"key":"215_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)"},{"key":"215_CR11","unstructured":"Cygan, M., Kowalik, \u0141., Pilipczuk, M.: Open Problems from Workshop on Kernels. Worker 2013 (2013)"},{"key":"215_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., van Leeuwen, E.J., Wrochna, M.: Polynomial kernelization for removing induced claws and diamonds. In: Graph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, pp. 440\u2013455 (2015)","DOI":"10.1007\/978-3-662-53174-7_31"},{"key":"215_CR13","doi-asserted-by":"crossref","unstructured":"Drange, P.G., Dregi, M.S., Sandeep, R.B.: Compressing bounded degree graphs. In: LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, pp. 362\u2013375 (2016)","DOI":"10.1007\/978-3-662-49529-2_27"},{"key":"215_CR14","doi-asserted-by":"crossref","unstructured":"Drange, P.G., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. In: Algorithms - ESA 2015 - 23rd Annual European Symposium, pp. 424\u2013436 (2015)","DOI":"10.1007\/978-3-662-48350-3_36"},{"issue":"3","key":"215_CR15","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"ES El-Mallah","year":"1988","unstructured":"El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst. 35(3), 354\u2013362 (1988)","journal-title":"IEEE Trans. Circuits Syst."},{"issue":"3","key":"215_CR16","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."},{"issue":"4","key":"215_CR17","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1007\/s00453-013-9837-5","volume":"71","author":"E Ghosh","year":"2013","unstructured":"Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.: Faster parameterized algorithms for deletion to split graphs. Algorithmica 71(4), 989\u20131006 (2013)","journal-title":"Algorithmica"},{"issue":"1","key":"215_CR18","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"PW Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2(1), 139\u2013152 (1995)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"215_CR19","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":"4","key":"215_CR20","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":"215_CR21","doi-asserted-by":"crossref","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Algorithms and Computation, 18th International Symposium, ISAAC 2007, pp. 915\u2013926 (2007)","DOI":"10.1007\/978-3-540-77120-3_79"},{"issue":"3","key":"215_CR22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"issue":"15","key":"215_CR23","doi-asserted-by":"crossref","first-page":"2259","DOI":"10.1016\/j.dam.2012.05.019","volume":"160","author":"C Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discrete Appl. Math. 160(15), 2259\u20132270 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"215_CR24","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(3), 193\u2013199 (2013)","journal-title":"Discrete Optim."},{"issue":"2","key":"215_CR25","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/j.jda.2007.04.001","volume":"6","author":"VB Le","year":"2008","unstructured":"Le, V.B., Mosca, R., M\u00fcller, H.: On stable cutsets in claw-free graphs and planar graphs. J. Discrete Algorithms 6(2), 256\u2013276 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"215_CR26","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"215_CR27","unstructured":"Liu, P., Geldmacher, R.: On the deletion of nonplanar edges of a graph. In: Proceedings on 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 727\u2013738 (1977)"},{"issue":"1","key":"215_CR28","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0166-218X(94)90214-3","volume":"49","author":"F Margot","year":"1994","unstructured":"Margot, F.: Some complexity results about threshold graphs. Discrete Appl. Math. 49(1), 299\u2013308 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"01","key":"215_CR29","doi-asserted-by":"crossref","first-page":"1250,008","DOI":"10.1142\/S1793830912500085","volume":"4","author":"J Nastos","year":"2012","unstructured":"Nastos, J., Gao, Y.: Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes. Discrete Math. Algorithms Appl. 4(01), 1250,008 (2012)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"215_CR30","doi-asserted-by":"crossref","unstructured":"Natanzon, A.: Complexity and approximation of some graph modification problems. Master\u2019s Thesis, Tel Aviv University (1999)","DOI":"10.1007\/3-540-46784-X_8"},{"issue":"1","key":"215_CR31","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109\u2013128 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"215_CR32","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131(3), 651\u2013654 (2003)","journal-title":"Discrete Appl. Math."},{"key":"215_CR33","unstructured":"Sandeep, R.B., Sivadasan, N.: Parameterized lower bound and improved kernel for diamond-free edge deletion. In: 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, pp. 365\u2013376 (2015)"},{"issue":"1","key":"215_CR34","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1), 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"key":"215_CR35","unstructured":"Sharan, R.: Graph modification problems and their applications to genomic research. Ph.D. thesis, Tel-Aviv University (2002)"},{"issue":"1","key":"215_CR36","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2(1), 77\u201379 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"2","key":"215_CR37","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0215-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0215-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0215-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T19:22:06Z","timestamp":1568402526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0215-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,23]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["215"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0215-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,23]]}}}