Fixed-parameter algorithms for DAG partitioning

DOI10.1016/J.DAM.2016.12.002zbMATH Open1355.05204arXiv1611.08809OpenAlexW2559697322MaRDI QIDQ507587FDOQ507587

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)

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.

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

Recommendations

• Parameterized complexity of DAG partitioning
• On a DAG partitioning problem
• Efficient algorithms for measuring the funnel-likeness of DAGs
• How to pack directed acyclic graphs into small blocks
• On finding optimal polytrees

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)

Cites Work

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

Cited In (6)

• On a DAG partitioning problem
• Parameterized complexity of DAG partitioning
• Efficient algorithms for measuring the funnel-likeness of DAGs
• Acyclic Digraphs
• Path partitions of phylogenetic networks
• Fractals for kernelization lower bounds

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)