Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!wuarchive!uwm.edu!linac!midway!msuinfo!buster.cps.msu.edu!linx
From: linx@buster.cps.msu.edu (Xiao-la Lin)
Newsgroups: comp.theory
Subject: information for an NP-complete problem
Message-ID: <1991Jun13.193720.27917@msuinfo.cl.msu.edu>
Date: 13 Jun 91 19:37:20 GMT
Sender: news@msuinfo.cl.msu.edu
Organization: Dept. of Computer Science, Michigan State University
Lines: 20
Originator: linx@buster.cps.msu.edu

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