home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2850 < prev    next >
Encoding:
Internet Message Format  |  1993-01-10  |  1.1 KB
  1. Path: sparky!uunet!crdgw1!rpi!think.com!ames!pacbell.com!network.ucsd.edu!munnari.oz.au!manuel.anu.edu.au!dubhe.anu.edu.au!tyl.anu.edu.au!not-for-mail
  2. From: bdm@cs.anu.edu.au (Brendan McKay)
  3. Newsgroups: comp.theory
  4. Subject: Is this NP-complete?
  5. Message-ID: <1ipgg2INNobm@tyl.anu.edu.au>
  6. Date: 10 Jan 93 15:48:18 GMT
  7. Distribution: inet
  8. Organization: Australian National University
  9. Lines: 17
  10. NNTP-Posting-Host: tyl.anu.edu.au
  11.  
  12. A generalised regular family (GRF) of sets is represented by a 
  13. vector (bot;top[1],...,top[n]) where bot and each top[i] are sets, 
  14. and each top[i] is a superset of bot.  The GRF consists of all  
  15. sets X such that bot <= X <= top[i] for some i, where "<=" means 
  16. "subset".  A _simple_ GRF is one with n=1.
  17.  
  18. INSTANCE:  A GRF F; and integer K >= 0.
  19. QUESTION:  Is F equal to the disjoint union of at most K
  20.            simple GRFs?
  21.  
  22. What is the complexity of this problem?  I suspect it is NP-complete
  23. but can't rule out some simple dynamic program (or something).
  24. This problem arose from a graph computation that runs faster
  25. if GRFs can be quickly split into a small number of simple GRFs.
  26.  
  27. Thanks,
  28. Brendan McKay.
  29.