Standard

Fixed-parameter algorithms for DAG Partitioning. / van Bevern, René; Bredereck, Robert; Chopin, Morgan и др.

в: Discrete Applied Mathematics, Том 220, 31.03.2017, стр. 134-160.

Результаты исследований: Научные публикации в периодических изданияхстатьяРецензирование

Harvard

van Bevern, R, Bredereck, R, Chopin, M, Hartung, S, Hüffner, F, Nichterlein, A & Suchý, O 2017, 'Fixed-parameter algorithms for DAG Partitioning', Discrete Applied Mathematics, Том. 220, стр. 134-160. https://doi.org/10.1016/j.dam.2016.12.002

APA

van Bevern, R., Bredereck, R., Chopin, M., Hartung, S., Hüffner, F., Nichterlein, A., & Suchý, O. (2017). Fixed-parameter algorithms for DAG Partitioning. Discrete Applied Mathematics, 220, 134-160. https://doi.org/10.1016/j.dam.2016.12.002

Vancouver

van Bevern R, Bredereck R, Chopin M, Hartung S, Hüffner F, Nichterlein A и др. Fixed-parameter algorithms for DAG Partitioning. Discrete Applied Mathematics. 2017 март 31;220:134-160. doi: 10.1016/j.dam.2016.12.002

Author

van Bevern, René ; Bredereck, Robert ; Chopin, Morgan и др. / Fixed-parameter algorithms for DAG Partitioning. в: Discrete Applied Mathematics. 2017 ; Том 220. стр. 134-160.

BibTeX

@article{79c37c11e2fb42a4a0ac4d5cdfdc4468,
title = "Fixed-parameter algorithms for DAG Partitioning",
abstract = "Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. (2009) as DAG PARTITIONING: given an arc-weighted directed acyclic graph on n  vertices and m  arcs, delete arcs with total weight at most  k such that each resulting weakly-connected component contains exactly one sink—a vertex without outgoing arcs. DAG PARTITIONING is NP-hard. We show an algorithm to solve DAG PARTITIONING in O(2k⋅(n+m))  time, that is, in linear time for fixed  k. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG PARTITIONING on simulated citation networks within five minutes for k≤190 and m being  107 and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.{\textquoteright}s heuristic. We show that Leskovec et al.{\textquoteright}s heuristic works optimally on trees and generalize this result by showing that DAG PARTITIONING is solvable in 2O(t2)⋅n time if a width-t tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian (2012). We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction.",
keywords = "Algorithm engineering, Evaluating heuristics, Graph algorithms, Linear-time algorithms, Multiway cut, NP-hard problem, Polynomial-time data reduction, KERNELIZATION, MULTIVARIATE ALGORITHMICS, COMPLEXITY",
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}",
note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",
year = "2017",
month = mar,
day = "31",
doi = "10.1016/j.dam.2016.12.002",
language = "English",
volume = "220",
pages = "134--160",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Fixed-parameter algorithms for 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

N1 - Publisher Copyright: © 2016 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2017/3/31

Y1 - 2017/3/31

N2 - Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. (2009) as DAG PARTITIONING: given an arc-weighted directed acyclic graph on n  vertices and m  arcs, delete arcs with total weight at most  k such that each resulting weakly-connected component contains exactly one sink—a vertex without outgoing arcs. DAG PARTITIONING is NP-hard. We show an algorithm to solve DAG PARTITIONING in O(2k⋅(n+m))  time, that is, in linear time for fixed  k. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG PARTITIONING on simulated citation networks within five minutes for k≤190 and m being  107 and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.’s heuristic. We show that Leskovec et al.’s heuristic works optimally on trees and generalize this result by showing that DAG PARTITIONING is solvable in 2O(t2)⋅n time if a width-t tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian (2012). We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction.

AB - Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. (2009) as DAG PARTITIONING: given an arc-weighted directed acyclic graph on n  vertices and m  arcs, delete arcs with total weight at most  k such that each resulting weakly-connected component contains exactly one sink—a vertex without outgoing arcs. DAG PARTITIONING is NP-hard. We show an algorithm to solve DAG PARTITIONING in O(2k⋅(n+m))  time, that is, in linear time for fixed  k. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG PARTITIONING on simulated citation networks within five minutes for k≤190 and m being  107 and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.’s heuristic. We show that Leskovec et al.’s heuristic works optimally on trees and generalize this result by showing that DAG PARTITIONING is solvable in 2O(t2)⋅n time if a width-t tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian (2012). We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction.

KW - Algorithm engineering

KW - Evaluating heuristics

KW - Graph algorithms

KW - Linear-time algorithms

KW - Multiway cut

KW - NP-hard problem

KW - Polynomial-time data reduction

KW - KERNELIZATION

KW - MULTIVARIATE ALGORITHMICS

KW - COMPLEXITY

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

U2 - 10.1016/j.dam.2016.12.002

DO - 10.1016/j.dam.2016.12.002

M3 - Article

AN - SCOPUS:85008685640

VL - 220

SP - 134

EP - 160

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -

ID: 9088023