From few components to an Eulerian graph by adding arcs

Manuel Sorge, René Van Bevern, Rolf Niedermeier, Mathias Weller

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

15 Citations (Scopus)

Abstract

Eulerian Extension (EE) is the problem to make an arc-weighted directed multigraph Eulerian by adding arcs of minimum total cost. EE is NP-hard and has been shown fixed-parameter tractable with respect to the number of arc additions. Complementing this result, on the way to answering an open question, we show that EE is fixed-parameter tractable with respect to the combined parameter "number of connected components in the underlying undirected multigraph" and "sum of indeg(v) - outdeg(v) over all vertices v in the input multigraph where this value is positive." Moreover, we show that EE is unlikely to admit a polynomial-size problem kernel for this parameter combination and for the parameter "number of arc additions".

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers
Pages307-318
Number of pages12
DOIs
Publication statusPublished - 1 Dec 2011
Externally publishedYes
Event37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 - Tepla Monastery, Czech Republic
Duration: 21 Jun 201124 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6986 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011
CountryCzech Republic
CityTepla Monastery
Period21.06.201124.06.2011

Fingerprint Dive into the research topics of 'From few components to an Eulerian graph by adding arcs'. Together they form a unique fingerprint.

Cite this