[comp.theory] Reference needed on partition graph into modules

liu@mangani.ucsd.edu (Hai-Ning Liu) (10/27/90)

We are doing research in graph partition
and would like to get reference relate to the following problem. 

Given a directed acyclic graph (dag)\  $G(V,E)$
and a positive integer $  m $,
one wants to find a partition of $  V $ into disjoint
sets $ A_1 , A_2 , ... , A_t $   
such that the resulted digraph $ K ( X , U ) $ 
has the following property:
$  K ( X , U ) $ has the minimal number of edges.
Here $ X = \{  A_1 , A_2 , ..., A_t \} $ 
with $  | A_i | \leq m $  
for each $  1 \leq i \leq t $,
and $ ( A_i , A_j ) \in U $ if
and only if $ ( v_i , v_j ) \in E $ 
for some $ v_i \in A_i $ and $  v_j \in A_j .$ 

We have shown that the problem is NP-complete.

Please email me and I will post the summary if enough interests exist.
Thank you,

---H.-N. Liu