You are already planning a party for spring break! You have a large a group of f

Question

You are already planning a party for spring break! You have a large a group of friends, but not all of your friends are friends with each other (and you know of all the friendships between your friends). You wish to invite as many friends as possible to the party, but you do not want anyone to be lonely. So, you decide that you will select a subset of friends such that each invitee has at least 5 friends among the other invitees. Define an O(m)-time algorithm that finds such a subset of maximum size, where m is the total number of friendships among your friends.

Explanation / Answer

Label the people that could be invited 1, . . . n.

For a subset S of {1, 2, . . . , n}, define Ki(S) to be the number of people in S that the ith person knows.

Then the algorithm is:

• Let P = {1, 2, . . . , n} be the set of potential invitees.

• While there exists i P such that Ki(P) >= 5 : P P {i}.

• Return P.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.