2
$\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.

Improve this question
$\endgroup$
9
  • $\begingroup$ What do you mean by "exchange vertices with edges"? $\endgroup$
    – Louis
    May 13, 2014 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, 2014 at 16:59
  • $\begingroup$ It's a replacement vertx-edge. $\endgroup$
    – Pedro
    May 13, 2014 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, 2014 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, 2014 at 19:23

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2014 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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