Parameterized complexity of DAG partitioning. (English) Zbl 1382.68127

van Bevern, René; Bredereck, Robert; Chopin, Morgan; Hartung, Sepp; Hüffner, Falk; Nichterlein, André; Suchý, Ondřej

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

MSC:

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