Parameterized Complexity of DAG Partitioning
André Nichterlein (Ph.D student, TU Berlin)
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
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*n2) 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 is a subset of coNP/poly. Finally, given a tree decomposition of width w, we show how to solve DAG Partitioning in 2^(O(w2))*n time, improving a known algorithm for the parameter pathwidth.
Back to the research colloquium site.