# Why can't we solve the dinner party problem by finding a maximum matching?

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):

1. We create a graph where vertices are acquaintances, and edges are "not on speaking terms with each other".
2. We exchange vertices with edges.
3. We find a maximum matching, and these edges are the guests I can invite.

EDIT: I explain it better:

1. 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.
2. We find a maximum matching, and these edges are the guests I can invite.

But I'm not sure why I'm wrong.

• What do you mean by "exchange vertices with edges"? – Louis May 13 '14 at 16:44
• I mean, where I have a vertex I put an edge, where I have an edge I put a vertex. Now acquaintances are the edges. There is no problem if i have to put an extra vertex because an edge is now alone at an end . Sorry for my english – Pedro May 13 '14 at 16:59
• It's a replacement vertx-edge. – Pedro May 13 '14 at 17:04
• Imagen i have this: v---v---v. I exchange: ---v---v--- Now I put extra V because i have edges at the ends: v---v---v---v So the maximum matching is 2. I only can invite these two guys. – Pedro May 13 '14 at 17:09
• @Pedro You're still not defining your graph clearly. As far as I can understand, the vertices in the new graph correspond to the original edges. When do you connect two vertices $(x,y),(z,w)$? When they share an original vertex? This way each original vertex would correspond to many new edges. – Yuval Filmus May 13 '14 at 19:23