Simple path in a graph, within a given range of lengths Given an undirected graph $G(V,E)$ and two nodes $s$ and $t$, $s,t\in V$, find a path whose length $L$ is bounded by a lower bound $N$ and an upper bound $M$, $N\leq L\leq M$.

So, for example, $N=4, M=7$, I want to confirm that there is at least one simple path of 4,5,6 and 7 between two nodes in a graph? Nodes of the graph may appear in more than one path.

Typical problem size:  


10,000 nodes   
Mean of 20 edges per node   
Cycles in graph  
Unweighted edges
A special case of your problem is to determine whether there is a path of length between $n-1$ and $n-1$ (sic) in an $n$-vertex graph. This is the Hamiltonian path problem, which is well known to be NP-complete, so your problem is also NP-complete. More generally, it's also NP-complete to determine if a graph has a path of length at least&nbsp;$k$ (i.e., between $k$ and $n-1$) between two given vertices.