Minimum number of people required to invite everyone to a reunion

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.

• 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. Jan 3, 2014 at 12:14

• 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]. Jan 4, 2014 at 4:50