Problem Detail: 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.
Asked By : Pedro
Answered By : FrankW
The problem is that you can not model all instances of the problem in the way you suggest: A person can be ‘not on speaking terms’ with arbitrarily many other persons, but an edge in a graph can only be connected to two vertices. So instances where someone doesn’t want to speak to 3 or more other people cannot be modeled.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24682
