home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1824 < prev    next >
Encoding:
Internet Message Format  |  1992-08-25  |  2.2 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!GS6.SP.CS.CMU.EDU!jmount
  2. From: jmount+@CS.CMU.EDU (John Mount)
  3. Newsgroups: comp.theory
  4. Subject: Re: Is this problem NP-complete?
  5. Message-ID: <BtK6A4.HzL.2@cs.cmu.edu>
  6. Date: 25 Aug 92 21:27:37 GMT
  7. Article-I.D.: cs.BtK6A4.HzL.2
  8. References: <1992Aug25.185050.11956@watson.ibm.com>
  9. Sender: news@cs.cmu.edu (Usenet News System)
  10. Followup-To: comp.theory
  11. Organization: Carnegie Mellon University
  12. Lines: 33
  13. Nntp-Posting-Host: gs6.sp.cs.cmu.edu
  14.  
  15. In article <1992Aug25.185050.11956@watson.ibm.com>, raghu@norway.fishkill.ibm.com (Raghu Hudli) writes:
  16. |> The problem is given a weighted graph G = (V,E) with positive weights
  17. |> for all edges in E, the weight of a vertex v_i in V is defined as the
  18. |> sum of the weights of edges incident on v_i. Find a subset S of V, such
  19. |> that |S| = K and the graph G' = ((V-S), E') has no vertex whose weight 
  20. |> is greater than a constant T. E' is  E - edges incident on vertices in S.
  21. |> 
  22. |> I have heuristic solutions for the problem that seem to work well. I wanted
  23. |> to make sure that I was not missing the optimum solution if the problem were
  24. |> not NP-complete. 
  25.  
  26. This problem is NP complete.  This is easy to see by reducing from the
  27. Independent Set problem (Garey and Johnson "Computers and
  28. Intractability": given G = (V,E) and N, find a subset S of V such that
  29. |S| = N and the induced subgraph has no edges), just set all the edges
  30. to be weight 1, T = 0 and K = |V| - N.
  31.  
  32. |> Thanks in advance for your response.
  33. |> 
  34. |> Raghu Hudli
  35. |> -----------------------------------------------------------------------
  36. |> Raghu V. Hudli                       Tel:   (914) 892-4188
  37. |> IBM Corporation                      Fax:   (914) 892-4316 
  38. |> E. Fishkill, NY                      email: raghu@vnet.ibm.com
  39. |> ------------------------------------------------------------------------
  40. |> Disclaimer: The opinions/views expressed here are mine and my employer
  41. |> does not necessarily concur with me.
  42.  
  43. -- 
  44. --- It is kind of strange being in CS theory, given computers really do exist.
  45. John Mount: jmount+@cs.cmu.edu               (412)268-6247
  46. School of Computer Science, Carnegie Mellon University, 
  47. 5000 Forbes Ave., Pittsburgh PA 15213-3891
  48.