Re: Is this an NP complete problem?

In comp.theory [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
# Hi, 
# 
# Could you give me some suggestions on this problem? Thanks for your
# time and attention first.
# 
# The problem I am thinking is as follows:
# 
# Given an undirected graph. Every edge in this graph will be in a
# specific color. Now I want to find a subset of edges that contains the
# least kinds of colors.
# 
# Is it an NP complete problem?

No, probably not.

Just take the empty set (in polynomial time).
It contains zero colors, and it will be hard 
to find something better.


 
# Finally thanks a lot for your time and attention once again.
# 
# Best regards,
# Helen
# 



--Gerhard


__________________________________________________________________
Gerhard J. Woeginger   http://wwwhome.cs.utwente.nl/~woegingergj/

[ comp.ai is moderated.  To submit, just post and be patient, or if ]
[ that fails mail your article to <[EMAIL PROTECTED]>, and ]
[ ask your news administrator to fix the problems with your system. ]