home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / theory / 2700 < prev    next >
Encoding:
Text File  |  1992-12-14  |  1.4 KB  |  44 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!brunix!brunix!as
  3. From: as@cs.brown.edu (Apratim Sarkar)
  4. Subject: NP-completeness question
  5. Message-ID: <1992Dec15.044307.9419@cs.brown.edu>
  6. Sender: news@cs.brown.edu
  7. Organization: Brown University Department of Computer Science
  8. Date: Tue, 15 Dec 1992 04:43:07 GMT
  9. Lines: 33
  10.  
  11.  
  12. I need to know whether the following problem is 
  13. NP-complete. Seems like that to me - but I can 
  14. not prove it.
  15. -----------------------------------------------
  16. Given an undirected unweighted graph (V,E) and
  17. given a subset R of V, delete the minimum number
  18. of edges so that all cycles involving at least 1
  19. node from R are deleted. That is, in the final
  20. solution, there may be cycles remaining in the
  21. graph, but none involving nodes from R.
  22.  
  23. When R=V, this is equivalent to finding the
  24. spanning tree of the graph and take the edge
  25. complement of it. This kills all the cycles in 
  26. the graph. 
  27.  
  28. When R={a} for some node a, it is equivalent to
  29. deleting d(a) - 1 adjacent incident edges of a,
  30. where d(a) is the degree of a. This kills all the
  31. cycles through a.
  32.  
  33. So the two extremes are P, but what about in the
  34. middle?
  35.  
  36. Any suggestions?
  37.  
  38. Thanks,
  39. Apra.
  40. ----------------------------------------------------------------------------------
  41. Apratim Sarkar                                              fone  (401)-863-7667 (off)    
  42. Brown University, Box 1910                                         (617)-262-5515 (home)
  43. Department of Computer Science                           fax   (401)-863-7657           
  44.