Complexity of finding all simple paths using depth first search?

Question

Thanks to everyone replying with ideas and alternate solutions. More efficient ways of solving problems are always welcome, as well as reminders to question my assumptions. That said, I'd like you to ignore for a moment what problem I'm trying to solve with the algorithm, and just help me analyze the big-Oh complexity of my algorithm as I've written it -- an all simple paths in a graph using depth-limited search as described here, and implemented here. Thanks!

Edit: This is homework, but I've already submitted this assignment and I'd just like to know if my answer correct. I get a little confused over Big-O complexity when recursion is involved.

---

Original question below:

I'm trying to find the complexity of an all-paths search as given by this algorithm. Given two vertices, I'm finding all simple paths between them using a depth-first search.

I know that the time complexity of DFS is O(V+E) and its space complexity is O(V), and my intuition is that the complexity of an all-paths search will be more than that, but I'm unable to determine what it will be.

Related SO questions here and here.

Update (in response to a comment below):

I'm trying to solve the six degrees of Kevin Bacon problem. This generally requires finding the lowest degree of separation between a pair of actors, but I have to find ALL degrees of separation (for now, less than 6, but this can change).

Answer 1

The worst-case scenario is (I think) the complete graph on n vertices. This graph has n! simple paths, and for each of them your algorithm does at least n^2 computational steps -- for each vertex adjacent to the last one in the path, it does a linear scan over the linked list of previously visited nodes. (That's not counting all the intermediate stages of the search.) So the complexity is at least O(n^2 * n!), possibly worse.

What's the larger problem you're trying to solve?

Answer 2

The 6 degrees is nice because it gives you a limitation. I realize the 6 can change, but I think the approach here still applies. Anywhere I say "6", just substitute in "# of degrees".

If you wanted, you could use Breadth First Search (BFS). If I understand correctly, you're given a starting point (an actor/actress) and you need to find all paths to an endpoint (Kevin Bacon) that are less than or equal to 6 edges away. You can break that down into subproblems by saying first find all the connections that are 1 edge away, then all the paths 2 edges away, ... , and finally find all the paths six edges away. This is exactly how a BFS would work...first examine all the nodes one edge away, then two, etc.

Alternately, you could also use a modified Depth First Search (DFS) by doing a normal DFS and follow each path as far as you can, but keep a counter and stop it from going more than 6 edges deep down any particular path.

I would think your solution will likely be much better than the normal O(V + E) simply because you're likely not visiting all Vertices or travelling along all Edges (assuming our graph is the relationships between a large numbers of actors), but rather you're constrained to a subgraph of the overall graph. You start off your search algorithm acting like you you're going to visit all vertices/edges, but regardless of whether you use BFS or DFS, you'll be stopping at 6 edges out from your starting vertex rather than looking through the entire graph.

Consider that something like DFS can be represented as O(V+E), but it can also be represented as O(b^d) where b is the branching factor and d is the graph depth (see Wikipedia_DFS for more info ). So given how many actors there are out there, what will b be? Given the constraints you know about the problem (6 degrees and what not), what will d be?

I think I've probably said enough. Hopefully that kickstarts it for you. I should add the caveat that I don't actually know the answer for sure, this is just how the problem strikes me ;)

Answer 3

I was thinking about using O((n^2)*depth) algorhitm

1. For each actor find all actors he was working whith. (O(n^2) space and time comlexity but both depends on actual number of connections and for most actors do not exceed 500 or 5x number of your friends on facebook) This brings 500*n time&space complexity.

2. Assemble whole three going over all people at same depth and append all of this connections. O(n^2*depth)

If you use doubly linked tree for storing connections you can find all connections in depth*n complexity

Answer 4

Answering my own question with my analysis, please comment/correct!

The algorithm is simplified and analyzed as follows: 
(Note: here MAXDEPTH is the maximum degrees of separation to search for, default 6)
1. For the current vertex, get neighbors (amortized O(1))
2. For every neighbor, do the following [O(b), where b is the branching factor, or the avg. number of neighbors of a vertex]
2.1.    Check if already visited [O(MAXDEPTH), since it’s a linked list of max size MAXDEPTH)
2.2.    Append path to paths list [amortized O(1)]
3. End for 
4. Do the following MAXDEPTH times [O(MAXDEPTH)]
4.1.    For every neighbor do the following [O(b)]
4.1.1.   Check if already visited [O(MAXDEPTH)]
4.1.2.   Add to visited list [O(1)]
4.1.3.   Recursively call search again [becomes O(MAXDEPTH*b)]
4.1.4.   Delete from visited list [O(1)]
4.2 End for /* Neighbor */
5. End loop /* MAXDEPTH */

Thus, the complexity becomes O((MAXDEPTH*b)^MAXDEPTH).