  This work addresses the NP-Hard problem of acyclic directed acyclic graph
(DAG) partitioning problem. The acyclic partitioning problem is defined as
partitioning the vertex set of a given directed acyclic graph into disjoint and
collectively exhaustive subsets (parts). Parts are to be assigned such that the
total sum of the vertex weights within each part satisfies a common upper bound
and the total sum of the edge costs that connect nodes across different parts
is minimized. Additionally, the quotient graph, i.e., the induced graph where
all nodes that are assigned to the same part are contracted to a single node
and edges of those are replaced with cumulative edges towards other nodes, is
also a directed acyclic graph. That is, the quotient graph itself is also a
graph that contains no cycles. Many computational and real-life applications
such as in computational task scheduling, RTL simulations, scheduling of
rail-rail transshipment tasks and Very Large Scale Integration (VLSI) design
make use of acyclic DAG partitioning. We address the need for a simple and
elegant mathematical formulation for the acyclic DAG partitioning problem that
enables easier understanding, communication, implementation, and
experimentation on the problem.
