I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers.
I'm interested in reading any proof of ACYCLIC PARTITION (Garey and Johnson) being NP-complete, and I'd love it if you could share a proof for the same here. It'd be great if you could also give an approximation algorithm for the problem.
EDIT:
The problem is defined as follows (Garey and Johnson):
Let $G = (V,A)$ be a directed graph, with a weight function $w(v)$ mapping each vertex $v$ to a positive integer, cost function $c(a)$ mapping each edge $a$ to a positive integer, and let there be two positive integers $B$ and $K$.
Is there a partition of V into disjoint sets $V1, V2,..., V_m$ such that the directed graph $G' = (V',A')$, where $V' = \{V1, V2,..., V_m\}$, and $(V_i, V_j)$ is in $A'$ if and only if $(v_i,v_j)$ is in $A$ for some $v_i \in V_i$ and some $v_j \in V_j$, is acyclic, such that the sum of the weights of the vertices in each $V_i$ does not exceed $B$, and such that the sum of the costs of all those arcs having their endpoints in different sets does not exceed $K$?