zbMATH — the first resource for mathematics

Parameterized complexity of DAG partitioning. (English) Zbl 1382.68127
Spirakis, Paul G. (ed.) et al., Algorithms and complexity. 8th international conference, CIAC 2013, Barcelona, Spain, May 22–24, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38232-1/pbk). Lecture Notes in Computer Science 7878, 49-60 (2013).
Summary: 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 } \cdot 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)} \cdot n ^{O(1)}\); further, DAG Partitioning does not have a polynomial kernel unless \(\mathrm{NP} \subseteq \mathrm{coNP/poly}\). Finally, given a tree decomposition of width \(w\), we show how to solve DAG Partitioning in \(2^{O(w^2)}\cdot n\) time, improving a known algorithm for the parameter pathwidth.
For the entire collection see [Zbl 1263.68023].

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI