3
$\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?

Improve this question
$\endgroup$
4
  • $\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, 2016 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, 2016 at 7:31
  • $\begingroup$ Is x,y,x a valid 2-edge path? ​ ​ $\endgroup$
    – user12859
    Aug 23, 2016 at 16:37
  • $\begingroup$ @RickyDemer yep! $\endgroup$
    – Steven Schmatz
    Aug 24, 2016 at 19:51

3 Answers 3

Reset to default
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,

Improve this answer
$\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.

Improve this answer
$\endgroup$
0
-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.

Improve this answer
$\endgroup$
4
  • 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, 2016 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, 2016 at 16:49
  • 2
    $\begingroup$ The question isn't asking about shortest paths! $\endgroup$
    – David Richerby
    Aug 24, 2016 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, 2016 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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