TY - GEN

T1 - From few components to an Eulerian graph by adding arcs

AU - Sorge, Manuel

AU - Van Bevern, René

AU - Niedermeier, Rolf

AU - Weller, Mathias

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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".

AB - 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".

UR - http://www.scopus.com/inward/record.url?scp=84855394417&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25870-1_28

DO - 10.1007/978-3-642-25870-1_28

M3 - Conference contribution

AN - SCOPUS:84855394417

SN - 9783642258695

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 307

EP - 318

BT - Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers

T2 - 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011

Y2 - 21 June 2011 through 24 June 2011

ER -