Time Complexity of DFS

Question

My understanding is that:
1) given a graph G with n vertices and m edges, DFS is O(n + m)
2) DFS can be used to produce a list of all simple paths between 2 vertices u and v

This would mean that DFS can produce a list of all simple paths between u and v in polynomial time.

However, if we could could list all simple paths between u and v in polynomial time, we should be able to decide if G has a Hamilton Path between u and v in polynomial time.

Since determining if G has a Hamilton Path is NP-Complete, my understanding must be incorrect. I'm hoping someone can clarify what I'm missing?

Answer 1

What you're missing is that there could be an exponential number of paths that stop short of connecting $u$ and $v$. Discovering these dead ends using depth-first search and backtracking is what makes DFS require worst-case exponential time to find a Hamiltonian path.

Answer 2

For traversing all the nodes, you will only visit each point for one time, thus linear time for traversing.

For finding all the paths, you might need to visit each node for many times(e.g. you need to backtrack to a node many times), and the number of possible paths is exponential thus exponential time for finding all paths.