Research output: Contribution to journal › Article › peer-review
Fixed-parameter algorithms for DAG Partitioning. / van Bevern, René; Bredereck, Robert; Chopin, Morgan et al.
In: Discrete Applied Mathematics, Vol. 220, 31.03.2017, p. 134-160.Research output: Contribution to journal › Article › peer-review
}
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