Fixed-parameter algorithms for DAG Partitioning. van Bevern, R., Bredereck, R., Chopin, M., Hartung, S., Hüffner, F., Nichterlein, A., & Suchý, O. Discrete Applied Mathematics, 220:134–160, 2017. ![Fixed-parameter algorithms for DAG Partitioning [link]](https://bibbase.org/img/filetypes/link.svg "link")
Preprint Code doi abstract bibtex 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 ( 2 k ⋅ ( 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 10 7 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 2 O ( t 2 ) ⋅ 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.
@article{BBC+17,
title = "Fixed-parameter algorithms for {DAG} Partitioning",
journal = "Discrete Applied Mathematics",
volume = 220,
pages = "134--160",
year = 2017,
issn = "0166-218X",
doi = "10.1016/j.dam.2016.12.002",
author = "René van Bevern and Robert Bredereck and Morgan
Chopin and Sepp Hartung and Falk Hüffner and André
Nichterlein and Ondřej Suchý",
keywords = "NP-hard problem",
keywords = "Graph algorithms",
keywords = "Polynomial-time data reduction",
keywords = "Multiway cut",
keywords = "Linear-time algorithms",
keywords = "Algorithm engineering",
keywords = "Evaluating heuristics ",
abstract = "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
( 2 k ⋅ ( 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 10 7
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
2 O ( t 2 ) ⋅ 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. ",
url_Preprint = {https://arxiv.org/abs/1611.08809},
url_Code = {https://gitlab.com/rvb/dagpart/}
}
Downloads: 0
{"_id":"wxfzwH868GiTa7EhQ","bibbaseid":"vanbevern-bredereck-chopin-hartung-hffner-nichterlein-such-fixedparameteralgorithmsfordagpartitioning-2017","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Bredereck, R.","Chopin, M.","Hartung, S.","Hüffner, F.","Nichterlein, A.","Suchý, O."],"bibdata":{"bibtype":"article","type":"article","title":"Fixed-parameter algorithms for DAG Partitioning","journal":"Discrete Applied Mathematics","volume":"220","pages":"134–160","year":"2017","issn":"0166-218X","doi":"10.1016/j.dam.2016.12.002","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Robert"],"propositions":[],"lastnames":["Bredereck"],"suffixes":[]},{"firstnames":["Morgan"],"propositions":[],"lastnames":["Chopin"],"suffixes":[]},{"firstnames":["Sepp"],"propositions":[],"lastnames":["Hartung"],"suffixes":[]},{"firstnames":["Falk"],"propositions":[],"lastnames":["Hüffner"],"suffixes":[]},{"firstnames":["André"],"propositions":[],"lastnames":["Nichterlein"],"suffixes":[]},{"firstnames":["Ondřej"],"propositions":[],"lastnames":["Suchý"],"suffixes":[]}],"keywords":"Evaluating heuristics ","abstract":"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 ( 2 k ⋅ ( 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 10 7 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 2 O ( t 2 ) ⋅ 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. ","url_preprint":"https://arxiv.org/abs/1611.08809","url_code":"https://gitlab.com/rvb/dagpart/","bibtex":"@article{BBC+17,\n title =\t \"Fixed-parameter algorithms for {DAG} Partitioning\",\n journal =\t \"Discrete Applied Mathematics\",\n volume =\t 220,\n pages =\t \"134--160\",\n year =\t 2017,\n issn =\t \"0166-218X\",\n doi =\t\t \"10.1016/j.dam.2016.12.002\",\n author =\t \"René van Bevern and Robert Bredereck and Morgan\n Chopin and Sepp Hartung and Falk Hüffner and André\n Nichterlein and Ondřej Suchý\",\n keywords =\t \"NP-hard problem\",\n keywords =\t \"Graph algorithms\",\n keywords =\t \"Polynomial-time data reduction\",\n keywords =\t \"Multiway cut\",\n keywords =\t \"Linear-time algorithms\",\n keywords =\t \"Algorithm engineering\",\n keywords =\t \"Evaluating heuristics \",\n abstract =\t \"Abstract Finding the origin of short phrases\n propagating through the web has been formalized by\n Leskovec et al. (2009) as \\{DAG\\} Partitioning:\n given an arc-weighted directed acyclic graph on n\n vertices and m arcs, delete arcs with total weight\n at most k such that each resulting weakly-connected\n component contains exactly one sink—a vertex without\n outgoing arcs. \\{DAG\\} Partitioning is NP-hard. We\n show an algorithm to solve \\{DAG\\} Partitioning in O\n ( 2 k ⋅ ( n + m ) ) time, that is, in linear time\n for fixed k . We complement it with linear-time\n executable data reduction rules. Our experiments\n show that, in combination, they can optimally solve\n \\{DAG\\} Partitioning on simulated citation networks\n within five minutes for k ≤ 190 and m being 10 7\n and larger. We use our obtained optimal solutions to\n evaluate the solution quality of Leskovec et al.’s\n heuristic. We show that Leskovec et al.’s heuristic\n works optimally on trees and generalize this result\n by showing that \\{DAG\\} Partitioning is solvable in\n 2 O ( t 2 ) ⋅ n time if a width- t tree\n decomposition of the input graph is given. Thus, we\n improve an algorithm and answer an open question of\n Alamdari and Mehrabian (2012). We complement our\n algorithms by lower bounds on the running time of\n exact algorithms and on the effectivity of data\n reduction. \",\n url_Preprint = {https://arxiv.org/abs/1611.08809},\n url_Code =\t {https://gitlab.com/rvb/dagpart/}\n}\n\n\n","author_short":["van Bevern, R.","Bredereck, R.","Chopin, M.","Hartung, S.","Hüffner, F.","Nichterlein, A.","Suchý, O."],"key":"BBC+17","id":"BBC+17","bibbaseid":"vanbevern-bredereck-chopin-hartung-hffner-nichterlein-such-fixedparameteralgorithmsfordagpartitioning-2017","role":"author","urls":{" preprint":"https://arxiv.org/abs/1611.08809"," code":"https://gitlab.com/rvb/dagpart/"},"keyword":["Evaluating heuristics"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":0,"html":""},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.488Z","downloads":0,"keywords":["evaluating heuristics"],"search_terms":["fixed","parameter","algorithms","dag","partitioning","van bevern","bredereck","chopin","hartung","hüffner","nichterlein","suchý"],"title":"Fixed-parameter algorithms for DAG Partitioning","year":2017,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}