{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T12:48:20Z","timestamp":1772714900256,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1007\/s00453-012-9667-x","type":"journal-article","created":{"date-parts":[[2012,6,21]],"date-time":"2012-06-21T22:55:46Z","timestamp":1340319346000},"page":"41-61","source":"Crossref","is-referenced-by-count":29,"title":["Parameterized Complexity of Eulerian Deletion Problems"],"prefix":"10.1007","volume":"68","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,6,22]]},"reference":[{"key":"9667_CR1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01585705","volume":"53","author":"R.K. Ahuja","year":"1992","unstructured":"Ahuja, R.K., Goldberg, A.V., Orlin, J.B., Tarjan, R.E.: Finding minimum-cost flows by double scaling. Math. Program. 53, 243\u2013266 (1992)","journal-title":"Math. Program."},{"key":"9667_CR2","first-page":"419","volume-title":"FOCS","author":"N. Alon","year":"2005","unstructured":"Alon, N., Shapira, A., Sudakov, B.: Additive approximation for edge-deletion problems. In: FOCS, pp. 419\u2013428. IEEE Comput. Soc., Los Alamitos (2005)"},{"issue":"4","key":"9667_CR3","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"3\u20134","key":"9667_CR4","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1007\/s00453-011-9492-7","volume":"62","author":"R. Bevern van","year":"2012","unstructured":"van Bevern, R., Moser, H., Niedermeier, R.: Approximation and tidying\u2014a problem kernel for s-plex cluster vertex deletion. Algorithmica 62(3\u20134), 930\u2013950 (2012)","journal-title":"Algorithmica"},{"key":"9667_CR5","series-title":"LIPIcs","first-page":"165","volume-title":"STACS","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: Schwentick, T., D\u00fcrr, C. (eds.) STACS. LIPIcs, vol. 9, pp. 165\u2013176. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2011)"},{"issue":"13","key":"9667_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":"1","key":"9667_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2005.01.002","volume":"198","author":"J. Cai","year":"2005","unstructured":"Cai, J., Chakaravarthy, V.T., Hemaspaandra, L.A., Ogihara, M.: Competing provers yield improved Karp-Lipton collapse results. Inf. Comput. 198(1), 1\u201323 (2005)","journal-title":"Inf. Comput."},{"issue":"4","key":"9667_CR8","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":"9667_CR9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.jda.2011.03.004","volume":"9","author":"L. Cai","year":"2011","unstructured":"Cai, L., Yang, B.: Parameterized complexity of even\/odd subgraph problems. J. Discrete Algorithms 9(3), 231\u2013240 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"9667_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/978-3-642-17493-3_9","volume-title":"IPEC","author":"K. Cechl\u00e1rov\u00e1","year":"2010","unstructured":"Cechl\u00e1rov\u00e1, K., Schlotter, I.: Computing the deficiency of housing markets with duplicate houses. In: Raman, V., Saurabh, S. (eds.) IPEC. Lecture Notes in Computer Science, vol. 6478, pp. 72\u201383. Springer, Berlin (2010)"},{"key":"9667_CR11","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of ACM 55(5) (2008)","DOI":"10.1145\/1411509.1411511"},{"key":"9667_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/11672142_29","volume-title":"STACS","author":"J. D\u00edaz","year":"2006","unstructured":"D\u00edaz, J., Thilikos, D.M.: Fast FPT-algorithms for cleaning grids. In: Durand, B., Thomas, W. (eds.) STACS. Lecture Notes in Computer Science, vol. 3884, pp. 361\u2013371. Springer, Berlin (2006)"},{"key":"9667_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/978-3-642-16926-7_11","volume-title":"WG","author":"F. Dorn","year":"2010","unstructured":"Dorn, F., Moser, H., Niedermeier, R., Weller, M.: Efficient algorithms for Eulerian extension. In: Thilikos, D.M. (ed.) WG. Lecture Notes in Computer Science, vol. 6410, pp. 100\u2013111. Springer, Berlin (2010)"},{"key":"9667_CR14","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.: Matching, Euler tours and the Chinese postman problem. Math. Program. 5, 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"9667_CR15","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9667_CR16","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"9667_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1007\/978-3-540-77120-3_79","volume-title":"ISAAC","author":"J. Guo","year":"2007","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Tokuyama, T. (ed.) ISAAC. Lecture Notes in Computer Science, vol. 4835, pp. 915\u2013926. Springer, Berlin (2007)"},{"key":"9667_CR18","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 289, 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"13","key":"9667_CR19","doi-asserted-by":"crossref","first-page":"2871","DOI":"10.1016\/j.dam.2009.03.018","volume":"157","author":"P. Kolman","year":"2009","unstructured":"Kolman, P., Pangr\u00e1c, O.: On the complexity of paths avoiding forbidden pairs. Discrete Appl. Math. 157(13), 2871\u20132876 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9667_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/978-3-642-11269-0_22","volume-title":"IWPEC","author":"S. Kratsch","year":"2009","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. In: Chen, J., Fomin, F.V. (eds.) IWPEC. Lecture Notes in Computer Science, vol. 5917, pp. 264\u2013275. Springer, Berlin (2009)"},{"issue":"2","key":"9667_CR21","doi-asserted-by":"crossref","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. J.\u00a0Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9667_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/978-3-540-79723-4_14","volume-title":"IWPEC","author":"D. Lokshtanov","year":"2008","unstructured":"Lokshtanov, D.: Wheel-free deletion is W[2]-hard. In: Grohe, M., Niedermeier, R. (eds.) IWPEC. Lecture Notes in Computer Science, vol. 5018, pp. 141\u2013147. Springer, Berlin (2008)"},{"issue":"4","key":"9667_CR23","doi-asserted-by":"crossref","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 57(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"key":"9667_CR24","series-title":"Conferences in Research and Practice in Information Technology","first-page":"79","volume-title":"CATS","author":"L. Mathieson","year":"2008","unstructured":"Mathieson, L., Szeider, S.: The parameterized complexity of regular subgraph problems and generalizations. In: Harland, J., Manyem, P. (eds.) CATS. Conferences in Research and Practice in Information Technology, vol. 77, pp. 79\u201386. Aust. Comput. Soc., Darlinghurst (2008)"},{"key":"9667_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1007\/978-3-540-77120-3_54","volume-title":"ISAAC","author":"H. Moser","year":"2007","unstructured":"Moser, H., Raman, V., Sikdar, S.: The parameterized complexity of the unique coverage problem. In: Tokuyama, T. (ed.) ISAAC. Lecture Notes in Computer Science, vol. 4835, pp. 621\u2013631. Springer, Berlin (2007)"},{"key":"9667_CR26","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.jda.2008.09.005","volume":"7","author":"H. Moser","year":"2009","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discrete Algorithms 7, 181\u2013190 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"9667_CR27","first-page":"182","volume-title":"FOCS","author":"M. Naor","year":"1995","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: FOCS, pp.\u00a0182\u2013191. IEEE Comput. Soc., Los Alamitos (1995)"},{"key":"9667_CR28","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, 109\u2013128 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9667_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/978-3-642-16926-7_19","volume-title":"WG","author":"G. Philip","year":"2010","unstructured":"Philip, G., Raman, V., Villanger, Y.: A quartic kernel for pathwidth-one vertex deletion. In: Thilikos, D.M. (ed.) WG. Lecture Notes in Computer Science, vol. 6410, pp. 196\u2013207 (2010)"},{"issue":"4","key":"9667_CR30","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J. Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199\u2013201 (1979)","journal-title":"Inf. Process. Lett."},{"key":"9667_CR31","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1016\/j.tcs.2005.10.010","volume":"351","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351, 446\u2013458 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9667_CR32","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.ipl.2007.05.005","volume":"104","author":"V. Raman","year":"2007","unstructured":"Raman, V., Sikdar, S.: Parameterized complexity of the induced subgraph problem in directed graphs. Inf. Process. Lett. 104, 79\u201385 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9667_CR33","unstructured":"Sorge, M.: On making directed graphs Eulerian. arXiv: 1101.4283v2 [cs.DM] (2011)"},{"key":"9667_CR34","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.K. Yap","year":"1983","unstructured":"Yap, C.K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9667-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T20:24:19Z","timestamp":1497990259000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9667-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,22]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9667"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9667-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,22]]}}}