Thread: Depth-first search & TSP

I believe b represents breadth and d represents depth in your b^d formula.

The fun part is that when you're solving TSP, the tree under consideration is not the n cities, but the n! paths; and TSP is indeed linear in n!.

Originally Posted by Cpro

I've read in a few places (a book I have and online articles) that the running time of Depth-First search is (O(|V| + |E|)), which is linear. In my implementation, I use it to solve the Traveling Salesman Problem, and the running time of Depth-first search grows exponentially, not linear.

The complexity depends on how you represent the graph. The running time given in Wikipedia assumes an adjacency list representation. Without being very rigorous, the idea is that in exploring the graph, each node is "visited" (in the sense that it's adjacency list is opened) exactly once, and each node's adjacency list is scanned exactly once. The number of nodes is O(|V|) and the sum of the lengths of all of the adjacency lists is O(|E|), hence O(|V| + |E|).

b is the branching factor -- the maximum degree (number of branches) at any node -- and d is the depth (the starting node is depth 0). The maximum possible number of nodes is b^d + b^(d-1) + ... b^0. The maximum number of edges is b^d + b^(d-1) + ... + b^1. Since the b^d term dominates all the lower-order terms, the complexity can be stated as O(b^d). Again, this assumes an adjacency list representation.

If you represent the graph as a matrix, you should be able to get O(|V|^2). If by exponentially, you mean that your DFS is O(something^|V|), that's bad.

Originally Posted by Cpro

Does this mean, that with respect to an adjacent list representation, the running time is (O(|V| + |E|)), while in general terms the running time is exponential?

PS: I use the adjacent list method in my implementation.


Thanks.

In general, you can't generalize. The complexity relates to the implementation, not the problem, except in the sense that for some problems you might be able to prove that "Algorithm X" is the most efficient possible algorithm. But even then, it would certainly be possible to come up with a worse algorithm, "Algorithm Y", so Algorithm Y's complexity would be worse than Algorithm X's complexity.

> Can you explain how it is linear in n!.
Just what it says -- the running time is a constant times n!. (Actually since you get to have the first city for free, it's really a constant times (n-1)!. But same deal.)

The |V|+|E| representation says that the running time will be a factor for each path you check (it takes some amount of time to check the distance for each path, times the number of paths) plus a factor for getting from one possible solution path to another (the edges between the nodes in your tree, times the number of times you have to change paths).

Originally Posted by Cpro

... are you saying that (O(|V| + |E|)) is independent of the algorithm used (in this case depth-first).

Absolutely not. In fact, I'm saying exactly the opposite - the complexity is the complexity of the algorithm, not the complexity of the problem. Furthermore, by algorithm, I mean exactly the specific implementation, not something like "DFS using an adjacency list representation in general". That (what I put in quotes) is not an algorithm, it's a category of algorithms.

Originally Posted by Cpro

Say I calculate the running time of my implementation and graph it, and I find the time complexity is n^2. Does that mean that the running time of my implementation using (O(|V| + |E|)) is also n^2?

Again, no. If your implementation is O(n^2), then it is not O(|V|+|E|). It is possible to write an O(|V|+|E|) implementation of DFS using an adjacency list representation of the graph. It is not guaranteed that every implementation is that efficient. You seem to have written one that isn't. The devil is in the details.

No, it's also Theta(|V|+|E|). I wrote O because I was lazy & you only seemed to be interested in the upper bound. Think about it - how could you do any search and be sure that it was complete without traversing every edge and visiting every node at least once?

Cpro, I think you may be confusing the complexity of an algorithm and the hardness of a problem. A complexity always refers to the algorithm as RS pointed out. But a problem can be proven to be Hard or Complete for a class such as NP. In this case, there cannot exist a polynomial time algorithm unless P = NP.

Originally Posted by brewbuck

DFS is too general a term to ascribe any particular complexity to it. I'm surprised Wikipedia claims any particular complexity at all. With the TSP, the problem is determining the global minimum. This provably can't be done without examining most of the possible paths, and this has nothing to do with DFS, it's just a fact.

Since TSP is NP-complete, it's certainly not linear in either |V| or |E|...

Actually it is linear in |V| and |E|. It just so happens the linear in |V| + |E| is the same as exponential in d.

It sounds counter intuitive but it's correct. It's like saying a 2-exp problem is linear in the number of states, which is true, but the number of states is 2 times exponential in the input size.