[algorithm] Find all paths between two graph nodes

I'm gonna give you a (somewhat small) version (although comprehensible, I think) of a scientific proof that you cannot do this under a feasible amount of time.

What I'm gonna prove is that the time complexity to enumerate all simple paths between two selected and distinct nodes (say, s and t) in an arbitrary graph G is not polynomial. Notice that, as we only care about the amount of paths between these nodes, the edge costs are unimportant.

Sure that, if the graph has some well selected properties, this can be easy. I'm considering the general case though.


Suppose that we have a polynomial algorithm that lists all simple paths between s and t.

If G is connected, the list is nonempty. If G is not and s and t are in different components, it's really easy to list all paths between them, because there are none! If they are in the same component, we can pretend that the whole graph consists only of that component. So let's assume G is indeed connected.

The number of listed paths must then be polynomial, otherwise the algorithm couldn't return me them all. If it enumerates all of them, it must give me the longest one, so it is in there. Having the list of paths, a simple procedure may be applied to point me which is this longest path.

We can show (although I can't think of a cohesive way to say it) that this longest path has to traverse all vertices of G. Thus, we have just found a Hamiltonian Path with a polynomial procedure! But this is a well known NP-hard problem.

We can then conclude that this polynomial algorithm we thought we had is very unlikely to exist, unless P = NP.

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to graph-theory

Why is the time complexity of both DFS and BFS O( V + E ) Find all paths between two graph nodes When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? Difference between hamiltonian path and euler path How to draw a graph in LaTeX? When should I use Kruskal as opposed to Prim (and vice versa)? Find the paths between two given nodes? Finding all cycles in a directed graph Cycles in an Undirected Graph Best algorithm for detecting cycles in a directed graph

Examples related to graph-algorithm

Find all paths between two graph nodes Negative weights using Dijkstra's Algorithm When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? Finding all cycles in a directed graph Why is the time complexity of both DFS and BFS O( V + E ) Find all paths between two graph nodes How to trace the path in a Breadth-First Search? How does a Breadth-First Search work when looking for Shortest Path? How do implement a breadth first traversal? When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? Performing Breadth First Search recursively Breadth First Vs Depth First