What makes it NP-hard? Naively, I would assume the number of simple paths between any two nodes in a graph to a polynomial function of the number of nodes plus the number of edges, so checking every path wouldn't be hard.
In the complete graph on n vertices, there are (n-2)! simple paths of length n-1 between any pair of distinct vertices, which is more than any polynomial in the number of vertices or edges.
