<p>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.</p>

CC BY-SA 2.5
2010-12-12T07:26:44.797Z
Actually, just BFS.  DFS won't give you the right results.
Jeffε
CC BY-SA 2.5
2010-12-10T13:59:48.983Z
2010-12-10T13:59:48.983Z
Dan Grossman
<p>You are looking for breadth-first search. O(n + m) and pretty simple to code.  If you want to calculate the number of shortest paths from a to b, there is a variant of breadth-first search described as an exercise in "Algorithm Design" by Kleinberg and Tardos which will do the job.</p>

<p>The algorithms work extremely quickly - I wrote a variant of this in Python to analyze a 30000 vertex / 100000 edge graph and the slowest part of the process was reading the graph data off the hard drive.</p>

CC BY-SA 2.5
2010-12-11T05:46:57.640Z
2010-12-11T05:46:57.640Z
Peter Boothe
<p>You want all solutions, so it is closer to <a href="http://en.wikipedia.org/wiki/Sharp-P-complete" rel="nofollow">http://en.wikipedia.org/wiki/Sharp-P-complete</a> type problems, although I don't think this is #P complete.</p>

<p>Highly symmetric graphs will yield large numbers as many paths will be the shortest from A->B.  Think of a torus grid when you are making paths between two points on opposite sides of the torus. </p>

CC BY-SA 2.5
2010-12-10T19:02:07.217Z
2010-12-10T19:02:07.217Z
Chad Brewbaker
<p>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).  </p>

<p>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.</p>

<p>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?</p>

<p>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)?  </p>

<p>Thanks</p>

<ds.algorithms><graph-algorithms><np><application-of-theory>
Is Degrees Of Separation NP Complete?
ircmaxell
# Is Degrees Of Separation NP Complete?

(Asked by: username_0 on 2010-12-10)

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

**Tags:** ds.algorithms, graph-algorithms, np, application-of-theory

---

## 3 answers

### Answer by username_1 on 2010-12-10. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: Actually, just BFS.  DFS won't give you the right results.  

---

### Answer by username_3 on 2010-12-11. Score: 3

You are looking for breadth-first search. O(n + m) and pretty simple to code. If you want to calculate the number of shortest paths from a to b, there is a variant of breadth-first search described as an exercise in "Algorithm Design" by Kleinberg and Tardos which will do the job.

The algorithms work extremely quickly - I wrote a variant of this in Python to analyze a 30000 vertex / 100000 edge graph and the slowest part of the process was reading the graph data off the hard drive.


---

### Answer by username_4 on 2010-12-10. Score: 0

You want all solutions, so it is closer to <http://en.wikipedia.org/wiki/Sharp-P-complete> type problems, although I don't think this is #P complete.

Highly symmetric graphs will yield large numbers as many paths will be the shortest from A->B. Think of a torus grid when you are making paths between two points on opposite sides of the torus.


---

