haochenkang's blog

Graph Problem
By haochenkang, history, 22 months ago, In English

Hi everyone,

I thought of a graph problem, It seems easy but I can't figure it out. Can someone help me with it?

Basically, there are N people that wants to join a party. However, you are given M pairs of people that cannot be with each other. Your task is to find out the maximum number of people that can be invited to the party.

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

This is a well-known problem called the Maximum Independent Set Problem, but there's no known solution that runs in polynomial time.

Two links if you wanted to learn more about it:

Wikipedia Maximal Independent Set

GeeksForGeeks Maximal Independent Set

→ Reply