## René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner,
André Nichterlein, and Ondřej Suchý.
Parameterized complexity of DAG partitioning.
In *Proceedings of the 8th International Conference on Algorithms
and Complexity (CIAC'13), Barcelona, Spain*, volume 7878 of *Lecture
Notes in Computer Science*, pages 49–60. Springer, 2013.
A final version of this article with improved algorithms and an
experimental evaluations has appeared in Discrete Applied Mathematics.

The goal of tracking the origin of short,
distinctive phrases (memes) that propagate through
the web in reaction to current events has been
formalized as DAG Partitioning: given a directed
acyclic graph, delete edges of minimum weight such
that each resulting connected component of the
underlying undirected graph contains only one
sink. Motivated by NP-hardness and hardness of
approximation results, we consider the parameterized
complexity of this problem. We show that it can be
solved in O(2^k·n^2) time, where k is the number of
edge deletions, proving fixed-parameter tractability
for parameter k. We then show that unless the
Exponential Time Hypothesis (ETH) fails, this cannot
be improved to 2^o(k)·n^O(1); further, DAG
Partitioning does not have a polynomial kernel
unless NP ⊆ coNP/poly. Finally, given a tree
decomposition of width w, we show how to solve DAG
Partitioning in 2^O(w^2)⋅n time, improving a known
algorithm for the parameter pathwidth.

[ bib |
DOI |
.pdf ]
Back

*This file was generated by
bibtex2html 1.98.*