Proof for ACYCLIC PARTITION being NP-complete 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$?
In the current formulation, your problem can be proved to be NP-complete by a direct reduction from PARTITION.

Given $n$ positive integers, $S = \{a_1,a_2,...,a_n\}$ the PARTITION problem asks to find two disjoint subsets $S_1 \cup S_2 = S$ such that $\sum_{i\in S_1} a_i = \sum_{j \in S_2} a_j$.

So, just pick: $G = \{ V, \emptyset \}$ with $|V| = n$, set $m = 2$ and assign weight $a_i$ to node $u_i$ for all $i = 1,...,n$; set $B = \frac{1}{2} \sum a_i$, and set $K=0$ (arc costs and the acyclic constraints are irrelevant).

NOTE: my old answer was related to a different ACYCLIC PARTITION problem, and you can find it in the edits history below.