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!

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

Thanks