Sie sind hier

## 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 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*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.

Date
Speaker
Location
Language
12.07.2012 16:15
André Nichterlein
TEL 512
english/german*