Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. From few components to an eulerian graph by adding arcs. In Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'11), Teplá Monastery, Czech Republic, volume 6986 of Lecture Notes in Computer Science, pages 307–318. Springer, 2011.

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”.

bib | DOI | .pdf ] Back


This file was generated by bibtex2html 1.98.