## The Birthday Party Problem

Next Tuesday is my happy birthday. As of now, I’m not planning to have a party. And based on some deep graph theoretic analysis that the wife and I just did over the last hour, it’s unlikely I will – for forming a coherent set of people to invite is an NP-hard problem, it seems like.

So five birthdays back we had a party, organised by the wife and meant as a surprise to me. On all counts it seemed like a great party. Except that the guests decided to divide themselves into one large clique and one smaller clique (of 2 people), leaving me as the cut vertex trying to bridge these cliques. That meant the onus was on me to make sure the tiny clique felt included in the party, and it wasn’t a lot of fun.

The problem is this – how do you invite a subset of friends for a party so that intervention by the host to keep guests entertained is minimised?

Let’s try and model this. Assume your friends network can be represented by an unweighted undirected graph, with a pair of friends being connected by an edge if they know (and get along with) each other already. Also assume you have full information about this graph (not always necessary).

The problem lies in selecting a subgraph of this graph such that you can be confident that it won’t break into smaller pieces (since that will mean you bonding with each such sub-group), and no guest feels left out (since the onus of making them comfortable will fall on you).

Firstly, the subgraph needs to be connected. Then, we can safely eliminate all guests who have degree of either zero or one (former is obvious, latter since they’ll be too needy on their only friend). In fact, we can impose a condition that each guest should have a minimum degree of two even in the subgraph.

Then we need to impose conditions on a group in the party breaking away. We can assume that for a group of people to break away, they need to be a clique (it is not a robust requirement, since you and someone you find at a party can suddenly decide to find a room, but reasonable enough).

We can also assume that for a group to break away, the strength of their mutual connections should outweigh the strength of their connections to the rest of the group. Since we’re using unweighted graphs here, we can simply assume that a group can break away if the number of edges between this group and the rest of the network is less than the size of the group.

So if there is a group of three who, put together, have two connections to the rest of the group, the group can break away. Similarly, a clique of four will break away from the main group if they have three or less edges going over. And let’s assume that the host is not a part of this subgroup of guests.

Given these constraints, and constraints on party size (minimum and maximum number of guests to invite), how can we identify an appropriate subset of friends to invite for the party? And I’m assuming this problem is NP-Hard (without thinking too much about it) – so can we think of a good heuristic to solve this problem

Do let me know the answer before next Tuesday, else I may not be able to have a party this time as well!

## Tim Harford on Christmas Cards

Tim Harford has a wonderful post out on the concept of Christmas cards. An extract:

But perhaps the Christmas card also serves other purposes. Consider the exchange, “How do you do?”, “How do you do?” This is phatic communication. It conveys no detailed information but it acknowledges others and implies that there is nothing much to report. “I’m OK, and you’re OK, and lines of communication are open if that changes.”

A Facebook “poke” could achieve the same thing at much lower cost. But perhaps the expense and the hassle is part of the point. If someone invites you for dinner and you say “thank you” as you leave, you may still wish to follow up with a thank-you note to show that you have enough invested in the relationship to take the trouble. If relationships weren’t hard work, they would not be relationships.

This is related to why when I greet people on occasions such as birthdays, anniversaries, etc. I make sure I do so over a mode of communication which opens up channels for further communication. So I either call (calling on birthdays is a bit dicey though since birthday boys/girls are flooded with calls – except if they’re me of course), or send an email or a one-to-one message using SMS or WhatsApp.

Any other means of communication makes it hard for further lines of communication to be open (think of someone politely typing “thank you” into a hundred “happy birthday” posts on their facebook wall), so it’s not worth the effort. And wishing on a WhatsApp group only results in everyone else on the group chiming in with a “happy birthday” and doesn’t lead to any conversation at all!

Coming back to Harford, his post also has some interesting fundaes on Dunbar’s Number. Read the whole thing.

PS: I’ve redacted my post on “performance art greetings”. Upon a second reading after I’d published it, I realised it was offensive towards certain people who I quite like and who I have no intention of offending. So I decided to take it down.