Fixed-parameter algorithms for DAG partitioning

DOI10.1016/J.DAM.2016.12.002MaRDI QIDQ507587zbMATH OpenOpenAlexFDO

Authors René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý

Publication date 6 February 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.08809

zbMATH Keywords

graph algorithmslinear-time algorithmsNP-hard problemalgorithm engineeringevaluating heuristicsmultiway cutpolynomial-time data reduction

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 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}cdot(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 $kleq190$ 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(w^2)}cdotn$ time if a width-$w$ tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian [WAW 2012]. We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction.

Recommendations

• Parameterized complexity of DAG partitioning
• On a DAG partitioning problem
• How to pack directed acyclic graphs into small blocks
• On finding optimal polytrees

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A general method to speed up fixed-parameter-tractable algorithms
• A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
• A shortcut to (sun)flowers: kernels in logarithmic space or linear time
• Applying modular decomposition to parameterized cluster editing problems
• Emergence of Scaling in Random Networks
• Fundamentals of parameterized complexity
• Infeasibility of instance compression and succinct PCPs for NP
• Introduction to algorithms
• Kernelization Lower Bounds by Cross-Composition
• Kernelization: new upper and lower bound techniques
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• New races in parameterized algorithmics
• On a DAG partitioning problem
• On the complexity of \(k\)-SAT
• Parameterized algorithms
• Parameterized complexity of DAG partitioning
• Parametrized complexity theory.
• Reflections on multivariate algorithmics and problem parameterization
• Simple and improved parameterized algorithms for multiterminal cuts
• Simpler linear-time kernelization for planar dominating set
• The Complexity of Multiterminal Cuts
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?

Cited in

(6)

• Path partitions of phylogenetic networks
• How to pack directed acyclic graphs into small blocks
• On a DAG partitioning problem
• Parameterized complexity of DAG partitioning
• Fractals for kernelization lower bounds
• Acyclic digraphs

This page was built for publication: Fixed-parameter algorithms for DAG partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507587)