[comp.theory] information for an NP-complete problem

linx@buster.cps.msu.edu (Xiao-la Lin) (06/14/91)

I post the following question for a friend in china.

He has proved the following probelm is NP-complete and he'd like
to know if it was proved by the others or not.

Instance: A collection of finite sets {s_1, s_2, ..., s_n}, an integer
k, k>0.

Question: Is there a collection of sets {t_1, t_2, ..., t_m} such that
    n       m
(1) U s_i = U t_j ;
   i=1     j=1
(2) m <= k ;
(3) For any i, j,  | s_i /\ t_j | <= 1.        /* /\  intersection */


If you know it was proved somewhere, would you please send me a mail?
Thanks much!

linx@frith.egr.msu.edu