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
  • $\begingroup$ I wonder, don't you already have a practical answer in your question on CSTheory? $\endgroup$ – Juho Feb 2 '14 at 16:32
  • $\begingroup$ What is the question? $\endgroup$ – Raphael Feb 3 '14 at 9:54

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 $k$ (i.e., between $k$ and $n-1$) between two given vertices.


I see this problem pretty close to the target-value search problem:

Given a graph $G(V,E)$ and a natural number $T$ find the path between the vertices $s, t\in V$ whose cost (or length in case of unary costs) is as close as possible to the given target value $T$

The latest reference on the question is, as far as I can tell Target-Value Search Revisited which was recently published at the International Joint Conference on Artificial Intelligence ---admittedly, this is a paper of my own, sorry for self-referencing my own work but I do see your question closely related to this other one.

Just invoke the target-value search algorithm with a target value equal to the average $T=\lfloor\frac{N+M}{2}\rfloor$ and there you go, it will find the path with the cost closer to it thus solving your problem. There is only a caveat and it is that if $N+M$ is an odd number the algorithm might prefer a solution with a cost equal to $\lfloor\frac{N+M}{2}\rfloor-\lceil\frac{M-N}{2}\rceil$ instead of $M$ (note that the first term is strictly less than $N$ iff $N+M$ is an odd number), but there are various ways to solve this problem efficiently.

Finally, the algorithm pursues paths with a cost as close as possible to the given target value $T$. In case you are interested in the length instead, then just provide graphs with unary costs.

In case you are interested I can provide you with source code (in C++) that implements target-value search. I made experiments with graphs as those you mention (but shorter branching factors) and it effectively finds optimal solutions pretty fast (in less than a second). Moreover, if you do not mind, I would be happy to make experiments with your domains in case you have any at hand that you could send me.

Hope this helps,


Not the answer you're looking for? Browse other questions tagged or ask your own question.