dc.contributor.author | Cygan, Marek | eng |
dc.contributor.author | Pilipczuk, Marcin | eng |
dc.contributor.author | Marx, Dániel | eng |
dc.contributor.author | Pilipczuk, Michal Pawel | eng |
dc.contributor.author | Schlotter, Ildikó | eng |
dc.date.accessioned | 2015-03-12T09:18:12Z | |
dc.date.available | 2015-03-12T09:18:12Z | |
dc.date.issued | 2014-01 | eng |
dc.identifier.issn | 0178-4617 | en_US |
dc.identifier.issn | 1432-0541 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/9520 | |
dc.description.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. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Springer | en_US |
dc.rights | Attribution CC BY | eng |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0/ | eng |
dc.subject | Fixed-parameter tractability | eng |
dc.subject | Kernelization | eng |
dc.subject | Eulerian graph | eng |
dc.subject | Deletion distance | eng |
dc.title | Parameterized complexity of Eulerian deletion problems | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2015-03-05T08:06:46Z | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright The Author(s) 2012 | en_US |
dc.identifier.doi | https://doi.org/10.1007/s00453-012-9667-x | |
dc.identifier.cristin | 1016626 | |
dc.source.journal | Algorithmica | |
dc.source.40 | 68 | |
dc.source.14 | 1 | |
dc.source.pagenumber | 41-61 | |
dc.subject.nsi | VDP::Mathematics and natural scienses: 400::Information and communication science: 420::Algorithms and computability theory: 422 | en_US |
dc.subject.nsi | VDP::Matematikk og naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420::Algoritmer og beregnbarhetsteori: 422 | nob |