### Page Content

### to Navigation

## 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*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 is a subset of 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.

Date | Speaker | Location | Language |
---|---|---|---|

12.07.2012 16:15 | André Nichterlein | TEL 512 | english/german* |