zbMATH — the first resource for mathematics

On a DAG partitioning problem. (English) Zbl 1342.05109
Bonato, Anthony (ed.) et al., Algorithms and models for the web graph. 9th international workshop, WAW 2012, Halifax, NS, Canada, June 22–23, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-30540-5/pbk). Lecture Notes in Computer Science 7323, 17-28 (2012).
Summary: We study the following DAG partitioning problem: given a directed acyclic graph with arc weights, delete a set of arcs of minimum total weight so that each of the resulting connected components has exactly one sink. We prove that the problem is hard to approximate in a strong sense: If $$\mathcal P\neq \mathcal{NP}$$ then for every fixed $$\epsilon > 0$$, there is no $$(n ^{1 - \epsilon })$$-approximation algorithm, even if the input graph is restricted to have unit weight arcs, maximum out-degree three, and two sinks. We also present a polynomial time algorithm for solving the DAG partitioning problem in graphs with bounded pathwidth.
For the entire collection see [Zbl 1241.68009].

MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C82 Small world graphs, complex networks (graph-theoretic aspects) 05C12 Distance in graphs 05C22 Signed and weighted graphs 05C40 Connectivity 05C20 Directed graphs (digraphs), tournaments 68Q25 Analysis of algorithms and problem complexity
Full Text: