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.

Preview

PDF (Creative Commons : Attribution 4.0) WRAP_art%3A10.1007%2Fs00453-012-9667-x.pdf - Published Version - Requires a PDF viewer. Download (874Kb) | Preview

Request Changes to record.

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:	Date Event 1 January 2014 Published 22 June 2012 Available 6 June 2012 Accepted 11 December 2011 Submitted
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