title: Parameterized Complexity of Eulerian Deletion Problems.
abstract: We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. The collection of results shows an interesting contrast: while the node-deletion variants remain intractable, i.e., W[1]-hard for all the studied cases, edge-deletion problems are either fixed-parameter tractable or polynomial-time solvable. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges, based on a novel application of the color coding technique. For versions that remain NP-complete but fixed-parameter tractable we consider also possibilities of polynomial kernelization; unfortunately, we prove that this is not possible unless NP⊆coNP/poly.
authors.affiliation: Institute of Informatics, University of Warsaw, ul. Banacha 2, 02-097, Warsaw, Poland.
authors.forename: Marek
authors.initials: M
authors.lastname: Cygan
authors.affiliation: Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany.
authors.forename: Dániel
authors.initials: D
authors.lastname: Marx
authors.affiliation: Institute of Informatics, University of Warsaw, ul. Banacha 2, 02-097, Warsaw, Poland.
authors.forename: Marcin
authors.initials: M
authors.lastname: Pilipczuk
authors.affiliation: Department of Informatics, University of Bergen, Postboks 7803, 5020 Bergen, Norway.
authors.forename: Michał
authors.initials: M
authors.lastname: Pilipczuk
authors.affiliation: Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar tudósok körútja 2, 1117 Budapest, Hungary.
authors.forename: Ildikó
authors.initials: I
authors.lastname: Schlotter
keywords: Deletion distance; Eulerian graph; Fixed-parameter tractability; Kernelization