1
$\begingroup$

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
$\endgroup$
  • $\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
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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,

| cite | improve this answer | |
$\endgroup$

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