How to Pack Directed Acyclic Graphs into Small Blocks

摘要

The paper studies the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short), the objective is to find a mapping of its nodes into blocks of size at most B that minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. The problem can be shown to be NP-hard generally, and to remain intractable even if B = 2 and the height of DAGs is three. In this paper we provide a 3/2 factor linear time approximation algorithm for 8 = 2, and prove that the 3/2 ratio is optimal in terms of approximation guarantee. In the case of B ≥ 3, we also show that there is no 3/2 — ε factor approximation algorithm assuming P ≠ NP, where ε is arbitrarily small positive. Furthermore, we give a 2 factor approximation algorithm for B = 3 if the input is restricted to a set of layered graphs.