Standard
Parameterized complexity of DAG partitioning. / Van Bevern, René; Bredereck, Robert; Chopin, Morgan et al.
Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. p. 49-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Van Bevern, R, Bredereck, R, Chopin, M, Hartung, S, Hüffner, F, Nichterlein, A & Suchý, O 2013,
Parameterized complexity of DAG partitioning. in
Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7878 LNCS, pp. 49-60, 8th International Conference on Algorithms and Complexity, CIAC 2013, Barcelona, Spain,
22.05.2013.
https://doi.org/10.1007/978-3-642-38233-8_5
APA
Van Bevern, R., Bredereck, R., Chopin, M., Hartung, S., Hüffner, F., Nichterlein, A., & Suchý, O. (2013).
Parameterized complexity of DAG partitioning. In
Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings (pp. 49-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS).
https://doi.org/10.1007/978-3-642-38233-8_5
Vancouver
Van Bevern R, Bredereck R, Chopin M, Hartung S, Hüffner F, Nichterlein A et al.
Parameterized complexity of DAG partitioning. In Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. p. 49-60. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-38233-8_5
Author
Van Bevern, René ; Bredereck, Robert ; Chopin, Morgan et al. /
Parameterized complexity of DAG partitioning. Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. pp. 49-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{a90fef5f46ef43fb9fded36c22792997,
title = "Parameterized complexity of DAG partitioning",
abstract = "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.",
author = "{Van Bevern}, Ren{\'e} and Robert Bredereck and Morgan Chopin and Sepp Hartung and Falk H{\"u}ffner and Andr{\'e} Nichterlein and Ond{\v r}ej Such{\'y}",
year = "2013",
month = sep,
day = "9",
doi = "10.1007/978-3-642-38233-8_5",
language = "English",
isbn = "9783642382321",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "49--60",
booktitle = "Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings",
note = "8th International Conference on Algorithms and Complexity, CIAC 2013 ; Conference date: 22-05-2013 Through 24-05-2013",
}
RIS
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 -
