1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by "exchange vertices with edges"? $\endgroup$ – Louis May 13 '14 at 16:44
  • $\begingroup$ 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 $\endgroup$ – Pedro May 13 '14 at 16:59
  • $\begingroup$ It's a replacement vertx-edge. $\endgroup$ – Pedro May 13 '14 at 17:04
  • $\begingroup$ 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. $\endgroup$ – Pedro May 13 '14 at 17:09
  • 1
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus May 13 '14 at 19:23
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh! Of course...oh, now I see, I misunderstood the problem... I do not know why I thought that a person only appeared two times. What an idiot I am! Thank you. $\endgroup$ – Pedro May 14 '14 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.