Is Degrees Of Separation NP Complete? I'm doing a bit of research on doing social analysis between so called "hub" people.  Basically what I want to try to do is determine the shortest paths between two individuals.  The problem is that while there are relatively few individuals (a few hundred at most), there are a LOT more connections between the nodes (and several categories of connections).  So while a graph may have 100 nodes, there may be tens of thousands of connections (Some of which are redundant).  

Now, what we want to try to do is show the relationships from each individual to each other.  So for example, if you pick person A, show all of their first degree relationships.  Then show all second degree relationships, etc until all the relationships are shown.

There may be as many as 1000 nodes and 100,000 connections, but I don't think too much more than that.  Are there any simple algorithms available for this, or would pre-computing unique permutations (via a Map-Reduce style system) be my best bet?

Am I right by thinking this problem is a NP problem (I don't think it's NP-Complete, but it might by NP-Hard)?  

Thanks
You can create a table with the degrees-of-separation between every two users by doing a BFS or DFS from each node and recording the length of the shortest path to each node you reach as you get there (sometimes replacing a larger value with a shorter one through a different path you explored later). That's definitely polynomial time (O(|V|^2 + |V|*|E|)), but that's not to say it's cheap to do.