{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:42:08Z","timestamp":1772372528394,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2017,12,28]],"date-time":"2017-12-28T00:00:00Z","timestamp":1514419200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["UMO-2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-017-0401-6","type":"journal-article","created":{"date-parts":[[2017,12,28]],"date-time":"2017-12-28T09:58:40Z","timestamp":1514455120000},"page":"3481-3524","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A Polynomial Kernel for Trivially Perfect Editing"],"prefix":"10.1007","volume":"80","author":[{"given":"P\u00e5l Gr\u00f8n\u00e5s","family":"Drange","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,12,28]]},"reference":[{"key":"401_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast fast. In: ICALP 2009, LNCS, vol. 5555, pp. 49\u201358. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_6"},{"issue":"4","key":"401_CR2","doi-asserted-by":"crossref","first-page":"1961","DOI":"10.1137\/140988565","volume":"29","author":"I Bliznets","year":"2015","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Pilipczuk, M.: A subexponential parameterized algorithm for proper interval completion. SIAM J. Discrete Math. 29(4), 1961\u20131987 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"401_CR3","doi-asserted-by":"crossref","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Pilipczuk, M.: Subexponential parameterized algorithm for interval completion. In: SODA 2016, pp. 1116\u20131131. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch78"},{"issue":"13","key":"401_CR4","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":"401_CR5","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":"401_CR6","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$$H-free edge modification problems. Algorithmica 71(3), 731\u2013757 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"401_CR7","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s00224-016-9689-x","volume":"60","author":"M Cygan","year":"2017","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., van Leeuwen, E.J., Wrochna, M.: Polynomial kernelization for removing induced claws and diamonds. Theory Comput. Syst. 60(4), 615\u2013636 (2017)","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"401_CR8","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and $$H$$H-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"401_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"401_CR10","unstructured":"Drange, P.G.: Parameterized graph modification algorithms. Ph.D. dissertation, University of Bergen, Norway (2015)"},{"key":"401_CR11","doi-asserted-by":"crossref","unstructured":"Drange, P.G., Dregi, M.S., Lokshtanov, D., Sullivan, B.D.: On the threshold of intractability. In: ESA 2015, LNCS, vol. 9294, pp. 411\u2013423. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_35"},{"issue":"4","key":"401_CR12","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/2799640","volume":"7","author":"PG Drange","year":"2015","unstructured":"Drange, P.G., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Exploring the subexponential complexity of completion problems. ACM Trans. Comput. Theory 7(4), 14:1\u201314:38 (2015)","journal-title":"ACM Trans. Comput. Theory"},{"key":"401_CR13","doi-asserted-by":"crossref","unstructured":"Drange, P.G., Pilipczuk, M.: A polynomial kernel for trivially perfect editing. In: ESA 2015, LNCS, vol. 9294, pp. 424\u2013436. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_36"},{"issue":"3","key":"401_CR14","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"3","key":"401_CR15","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"E El-Mallah","year":"1988","unstructured":"El-Mallah, E., Colbourn, C.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst. 35(3), 354\u2013362 (1988)","journal-title":"IEEE Trans. Circuits Syst."},{"key":"401_CR16","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, New York (2006)"},{"issue":"7","key":"401_CR17","doi-asserted-by":"crossref","first-page":"1430","DOI":"10.1016\/j.jcss.2014.04.015","volume":"80","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Villanger, Y.: Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci. 80(7), 1430\u20131447 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"401_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar $$F$$F-deletion: approximation, kernelization and optimal FPT algorithms. In: FOCS 2012, pp. 470\u2013479. IEEE (2012)","DOI":"10.1109\/FOCS.2012.62"},{"issue":"4","key":"401_CR19","doi-asserted-by":"crossref","first-page":"1964","DOI":"10.1137\/12089051X","volume":"27","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Saurabh, S., Villanger, Y.: A polynomial kernel for proper interval vertex deletion. SIAM J. Discrete Math. 27(4), 1964\u20131976 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"401_CR20","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1137\/11085390X","volume":"42","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. SIAM J. Comput. 42(6), 2197\u20132216 (2013)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"401_CR21","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hung. 18(1\u20132), 25\u201366 (1967)","journal-title":"Acta Math. Acad. Sci. Hung."},{"issue":"4","key":"401_CR22","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1007\/s00453-013-9837-5","volume":"71","author":"E Ghosh","year":"2015","unstructured":"Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.S.: Faster parameterized algorithms for deletion to split graphs. Algorithmica 71(4), 989\u20131006 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"401_CR23","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$$Pl-free edge modification problems. Algorithmica 65(4), 900\u2013926 (2013)","journal-title":"Algorithmica"},{"key":"401_CR24","doi-asserted-by":"crossref","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: ISAAC 2007, LNCS, vol. 4835, pp. 915\u2013926. Springer (2007)","DOI":"10.1007\/978-3-540-77120-3_79"},{"issue":"4","key":"401_CR25","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"401_CR26","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"Y Jing-Ho","year":"1996","unstructured":"Jing-Ho, Y., Jer-Jeong, C., Chang, G.J.: Quasi-threshold graphs. Discrete Appl. Math. 69(3), 247\u2013255 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"15","key":"401_CR27","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":"401_CR28","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":"4","key":"401_CR29","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1109\/TST.2014.6867517","volume":"19","author":"Y Liu","year":"2014","unstructured":"Liu, Y., Wang, J., Guo, J.: An overview of kernelization algorithms for graph modification problems. Tsinghua Sci. Technol. 19(4), 346\u2013357 (2014)","journal-title":"Tsinghua Sci. Technol."},{"key":"401_CR30","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.tcs.2011.11.040","volume":"461","author":"Y Liu","year":"2012","unstructured":"Liu, Y., Wang, J., Guo, J., Chen, J.: Complexity and parameterized algorithms for cograph editing. Theor. Comput. Sci. 461, 45\u201354 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"401_CR31","unstructured":"Mancini, F.: Graph modification problems related to graph classes. Ph.D. thesis, University of Bergen (2008)"},{"issue":"1\u20133","key":"401_CR32","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"issue":"3","key":"401_CR33","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/j.socnet.2013.05.001","volume":"35","author":"J Nastos","year":"2013","unstructured":"Nastos, J., Gao, Y.: Familial groups in social networks. Soc. Netw. 35(3), 439\u2013450 (2013)","journal-title":"Soc. Netw."},{"key":"401_CR34","unstructured":"Sandeep, R.B., Sivadasan, N.: Parameterized lower bound and improved kernel for diamond-free edge deletion. In: IPEC 2015, LIPIcs, vol. 43, pp. 365\u2013376. Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik (2015)"},{"issue":"1","key":"401_CR35","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Comb. Theory Ser. A 13(1), 145\u2013147 (1972)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"1","key":"401_CR36","doi-asserted-by":"crossref","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41(1), 247\u2013261 (1972)","journal-title":"Pac. J. Math."},{"issue":"2","key":"401_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-017-0401-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0401-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0401-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T16:15:59Z","timestamp":1570551359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0401-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,28]]},"references-count":37,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["401"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0401-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,28]]}}}