
The Library
Parameterized complexity of Eulerian deletion problems
Tools
Cygan, Marek, Marx, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał and Schlotter, Ildikó (2014) Parameterized complexity of Eulerian deletion problems. Algorithmica, Volume 68 (Number 1). pp. 41-61. doi:10.1007/s00453-012-9667-x ISSN 0178-4617.
|
PDF (Creative Commons : Attribution 4.0)
WRAP_art%3A10.1007%2Fs00453-012-9667-x.pdf - Published Version - Requires a PDF viewer. Download (874Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-012-9667-x
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.
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||
Library of Congress Subject Headings (LCSH): | Eulerian graph theory, Parameter estimation | ||||||||||
Journal or Publication Title: | Algorithmica | ||||||||||
Publisher: | Springer | ||||||||||
ISSN: | 0178-4617 | ||||||||||
Official Date: | 1 January 2014 | ||||||||||
Dates: |
|
||||||||||
Volume: | Volume 68 | ||||||||||
Number: | Number 1 | ||||||||||
Number of Pages: | 21 | ||||||||||
Page Range: | pp. 41-61 | ||||||||||
DOI: | 10.1007/s00453-012-9667-x | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||
Date of first compliant deposit: | 28 December 2015 | ||||||||||
Date of first compliant Open Access: | 28 December 2015 | ||||||||||
Funder: | Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP), Poland. Ministerstwo Nauki i Szkolnictwa Wyższego [Ministry of Science and Higher Education] (MNiSW), European Research Council (ERC), Országos Tudományos Kutatási Alapprogramok (OTKA), European Social Fund (ESF) | ||||||||||
Grant number: | N206 567140 (MNiSW), 267959 (ERC), OTKA 67651 (OTKA), TÁMOP 4.2.1./B-09/1/KMR-2010-0003 (ESF) | ||||||||||
Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year