Consider the following dinner party problem:
Given a list of acquaintances, and a list containing all pairs of individuals who are not on speaking terms with each other, find the largest set of acquaintances you can invite to a dinner party such that you do not invite any two who are not on speaking terms.
I have read in Arora-Barak that is not possible to find an efficient solution for the dinner party problem. I'm confused because I thought that it was easy to solve with Edmond's Blossom algorithm (it finds a maximum matching).
This is what I thought (of course it must be wrong):
- We create a graph where vertices are acquaintances, and edges are "not on speaking terms with each other".
- We exchange vertices with edges.
- We find a maximum matching, and these edges are the guests I can invite.
EDIT: I explain it better:
- We create a graph where edges are acquaintances and vertex are "not on speaking terms with each other" If the resulting graph has edges at the ends (it could be possible) we add extra vertex at these ends.
- We find a maximum matching, and these edges are the guests I can invite.
But I'm not sure why I'm wrong.