0
$\begingroup$

I'm trying to organise a large reunion though facebook. Over the years we've all drifted apart, and so there isn't anyone who is still facebook friends with everyone.

You need to be facebook friends to invite someone to the facebook event and I have invited all the people that I can. I also know that each of the uninvited people has at least one friend amongst the invited people, and by checking for 'mutual friends' I can know who they are.

In order to get everyone invited to the reunion I'm going to ask some of the invited people to invite the uninvited people.

My question is, does anyone happen to know an algorithm to find the minimum number of invited people that are required to message all of the uninvited people? I don't need anything super detailed, just something to point me in the right direction.

$\endgroup$
  • 2
    $\begingroup$ Since this is a real-life situation, an approximate solution will do just fine. You can quickly identify by eye a reasonably sized set of people who can invite most of the missing people and then deal with the rest ad hoc. That will be far faster than the data entry and programming you'd need to do to get an "optimal" solution and the whole thing will be dominated by the time it takes to message people asking them to invite specific other people anyway. On the off chance that this is actually homework, check out the dominating set problem. $\endgroup$ – David Richerby Jan 3 '14 at 12:14
1
$\begingroup$

One way to think about it is to make an undirected graph, and have every person be a vertex. There is an edge between two people if they are Facebook friends.

Now, assuming that you're asking people to invite their friends, and have those people invite their friends, and so on, then your problem basically boils down to finding the connected components of the graph you just made. (Two vertices are in the same connected component iff there exists a path between them)

Actually finding them isn't that bad; it's basically a slightly modified DFS.

$\endgroup$
  • 1
    $\begingroup$ This doesn't really answer OP's question in the sense that he/she wanted the minimum number of people to invite, so they may invite others. As David pointed out, this is the minimum dominating set problem which is NP-hard--an approximation may be necessary [the $O(\log n)$ greedy algorithm should work fine]. $\endgroup$ – Nicholas Mancuso Jan 4 '14 at 4:50
  • 1
    $\begingroup$ @NicholasMancuso That'd be true if you want the minimum people to invite, and they invite everyone else. I was talking about in the sense that you can have someone that was invited by someone who was invited by someone who was invited by someone, and so on. In that case, one person per connected component is enough. $\endgroup$ – Dennis Meng Jan 4 '14 at 4:56

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.