TY - GEN

T1 - Parameterized complexity of DAG partitioning

AU - Van Bevern, René

AU - Bredereck, Robert

AU - Chopin, Morgan

AU - Hartung, Sepp

AU - Hüffner, Falk

AU - Nichterlein, André

AU - Suchý, Ondřej

PY - 2013/9/9

Y1 - 2013/9/9

N2 - 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(2k·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 2o(k)·nO(1); further, DAG Partitioning does not have a polynomial kernel unless NP ⊆ coNP/poly. Finally, given a tree decomposition of width w, we show how to solve DAG Partitioning in 2o(w2)·n time, improving a known algorithm for the parameter pathwidth.

AB - 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(2k·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 2o(k)·nO(1); further, DAG Partitioning does not have a polynomial kernel unless NP ⊆ coNP/poly. Finally, given a tree decomposition of width w, we show how to solve DAG Partitioning in 2o(w2)·n time, improving a known algorithm for the parameter pathwidth.

UR - http://www.scopus.com/inward/record.url?scp=84883414008&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38233-8_5

DO - 10.1007/978-3-642-38233-8_5

M3 - Conference contribution

AN - SCOPUS:84883414008

SN - 9783642382321

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 60

BT - Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings

T2 - 8th International Conference on Algorithms and Complexity, CIAC 2013

Y2 - 22 May 2013 through 24 May 2013

ER -