Jason Kottke recently pondered what the minimum number of New York City residents one would need to choose, such that these people know every single person in the city:

Any guesses as to the smallest group size? Better yet, is there any research out there that specifically addresses this question? Or is it impossible…are there people living in the city (shut-ins, hermits) who don’t know anyone else?

People have been commenting about it on the blog, where the consensus seems to be about 10,000 people (this sounds pretty reasonable). My two-cents (which can be seen as the first comment on kottke) are reproduced here:

This is actually a well-established problem in graph theory called the vertex-cover problem. It is NP-hard, which means that there are no really good algorithms for it (although some approximate algorithms are good within a factor of two). In terms of answering this for NYC itself, my guess would be something on the order of 1000 or so. But I don’t have a good reason for that number, just a feeling. You could probably do better by assuming a power-law distribution for the number of acquaintances and derive a better estimate, but I haven’t thought about that in detail.