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.