4
$\begingroup$

Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d.

Output: A path between A and B with distance closest to d. The path need not be a simple path - it can contain repeated edges and vertices.

Which algorithms exist to solve this problem? I'm looking for an optimal solution, but I'm also interested to see if there are any approximation algorithms as well. Efficiency is not a huge concern - I just want to get an idea of the algorithms available.


Bonus question: are there any algorithms to compute a path from A to B that visits every node at least once, while finding the distance closest to d?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! Nice question. Do you want the output to be a simple path? Or can it contain repeated vertices and/or edges? Do you want an efficient algorithm, or any algorithm no matter how inefficient? You might want to look into the notion of cycle basis; I can imagine that might help with your first question. For your bonus question, I assume you know it is trivially NP-hard, since it's at least as hard as finding a Hamiltonian path? $\endgroup$ – D.W. Aug 23 '16 at 7:15
  • $\begingroup$ Thanks :) The path need not be a simple path - repeated edges and vertices are allowed. Efficiency is not a concern. I'll make sure to adjust the algorithm accordingly. $\endgroup$ – Steven Schmatz Aug 23 '16 at 7:31
  • $\begingroup$ Is x,y,x a valid 2-edge path? ​ ​ $\endgroup$ – user12859 Aug 23 '16 at 16:37
  • $\begingroup$ @RickyDemer yep! $\endgroup$ – Steven Schmatz Aug 24 '16 at 19:51
2
$\begingroup$

As far as I can tell, the first bibliographical reference I'm aware of within the context of heuristic search is Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleer, Rong Zhou, and Minh Do. Heuristic search for target-value path problem. In The First International Symposium on Search Techniques in Artificial Intelligence and Robotics, 2008. Since then, this problem is known as Target-Value Search, or TVS for short.

Similar ideas were then continued in another paper published the next year at SoCS (the Symposium on Combinatorial Search) but employing a depth-first search instead: Tim Schmidt, Lukas Kuhn, Bob Price, Johan de Kleer, and Rong Zhou. A depth-first approach to target-value search. In Symposium on Combinatorial Search (SOCS-09), 2009.

Interestingly, the algorithms described in these works solve the problem for graphs with arbitrary edge costs. However, they only perform experiments with tiny graphs (e.g., a few tens of nodes). Another team of researchers proposed a different algorithm for the case of unitary edge costs (ie., where all edge costs are restricted to be the same): Carlos Linares López, Roni Stern, Ariel Felner: Target-Value Search Revisited. IJCAI 2013: 601-607. They performed experiments with much larger graphs (ie., hundreds of thousands of nodes).

In this paper, the authors identified three different variants of the TVS. They originally addressed the case where vertices can be repeated but edges cannot be traversed twice.

That's not the case you are interested in! The specific case of simple paths was addressed in a short communication published in SoCS in 2014: Carlos Linares López, Roni Stern, Ariel Felner: Solving the Target-Value Search Problem. SOCS 2014. You will find in this paper the same reduction mentioned by D.W. from the SUBSET SUM PROBLEM to prove NP-hardness.

As mentioned above, however, the last two works are specific to the case where all edge costs are equal to one. All the algorithms mentioned in this response compute optimal solutions and I'm not aware of any approximation algorithms for solving this problem.

Hope this helps,

$\endgroup$
2
$\begingroup$

The problem is NP-hard, by reduction from subset sum (given weights $w_1,\dots,w_n$, take a graph with $n$ vertices and two edges from vertex $i$ to vertex $i+1$, one of weight zero and one of weight $w_i$).

One algorithm is to simply enumerate all paths up to a certain length (say, up to length $2d$, if all edge weights are non-negative). This can be done by enumerating all paths of length $i$; then enumerating all paths of length $i$ by concatenating any path of length $i$ followed by any edge out of the final vertex of that path; and so on, for $i=1,2,3,\dots$ Of course, the algorithm takes exponential time, but it is an algorithm.

$\endgroup$
-2
$\begingroup$

I could be wrong but this looks like a classic Dijkstra's algorithm problem. If you aren't familiar with the algorithm you can read more about it at Wikipedia, or you can read about the original variant of the algorithm from this paper written by Dijkstra himself here.

$\endgroup$
  • 3
    $\begingroup$ I could be wrong, too, but I think you're wrong. Dijkstra's algorithm finds the shortest simple path (no repetition of vertices) between two vertices; the question is looking for the path of length closest to some target and allows for repeated use of the same vertex or edge. $\endgroup$ – David Richerby Aug 24 '16 at 14:12
  • $\begingroup$ If a path is forced to use a repeated vertex, is it not, by definition, not the shortest path? $\endgroup$ – TheNamedOne Aug 24 '16 at 16:49
  • 2
    $\begingroup$ The question isn't asking about shortest paths! $\endgroup$ – David Richerby Aug 24 '16 at 17:15
  • 2
    $\begingroup$ The question says nothing about finding a shortest path. Indeed, the solution to the problem in the question will often fail to be a shortest path (and it may involve repeating a vertex or edge). $\endgroup$ – D.W. Aug 24 '16 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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