4
$\begingroup$

Is there a known algorithm for the following problem? Given a simple weighted directed graph, a pair of vertices $s$ and $t$, and a real value $k$, enumerate all simple paths from $s$ to $t$ with cost exactly $k$.

I've heard of uniform search, but I'm not really sure if it can solve my problem.

I just read that finding one $s$-$t$ path with a given cost is NP-hard in general. If all weights are $1$ and $k$ is one less than the number of vertices, this becomes the Hamiltonian Path Problem.

Improve this question
$\endgroup$
8
  • $\begingroup$ Can you give a link to the source that it is NP-hard? I was just trying to do the reduction from Hamiltonian Path and got stuck. $\endgroup$
    – usul
    Jan 31, 2013 at 9:08
  • 2
    $\begingroup$ Or did you want to make the additional restriction that all paths must be simple, i.e., touch each vertex at most once? In this case it is certainly NP-hard. $\endgroup$
    – usul
    Jan 31, 2013 at 9:16
  • 1
    $\begingroup$ Can the problem be formulated differently? I believe the number of paths of cost $k$ can grow exponentially in the number of vertices, i.e. the output is not polynomially bounded in the input. Is this really desired? $\endgroup$
    – user13407
    Jan 31, 2013 at 10:04
  • 3
    $\begingroup$ Actually, the way this is formulated, the case that there are exponentially many paths is the easy case. Because then, if you spend exponential time finding them, you still might only be spending polynomial time per path. The hard case is when there is only one path, because you may have to spend a lot of time finding it and can't share the cost of that search with any other paths. $\endgroup$
    – David Eppstein
    Jan 31, 2013 at 17:11
  • $\begingroup$ Surely if this problem is in P, then P = NP (or more precisely BPP = NP). Reduce SUBSET-SUM to it by creating a graph from an n-node path from S to T, where the weight of the i'th edge is the i'th number in the SUBSET-SUM instance, then add a weight-zero edge parallel to each edge in the path; take k to be the target for the SUBSET-SUM instance. (To deal with the issue of many possible paths, start by reducing UNIQUE-SAT to UNIQUE-SUBSET-SUM, then use UNIQUE-SUBSET-SUM instead. To ensure that the path must be simple, add some large N to each edge weight, and add n*N to k.) $\endgroup$
    – Neal Young
    Feb 2, 2013 at 0:30

1 Answer 1

Reset to default
3
$\begingroup$

I've been struggling for long with two similar problems and you are just referring to the combination of them: finding the best $K$ solutions and the Target-Value search problem. Since you are asking for algorithms, let me give you the best bib references I am aware of.

First, let me reformulate the second problem:

Given a graph $G(V,E)$ and a couple of vertices $s\in V$ and $t\in V$ find the simple path $P^*$ whose cost is as close as possible to a given value $k$, i.e., if $P_{s-t}$ denotes the set of all (simple) paths from $s$ to $t$ and $g(P)$ is the cost of a path which is defined as the sum of the cost of all of its edges, then $P^* = argmin_{\pi\in P_{s-t}} \{|c(\pi)-k|\}$

This problem is known as the Target-Value search problem and was originally introduced in Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleeer, Rong Zhou and Minh Do, Heuristic Search for Target-Value Path Problem. In case a path actually exists with a cost equal to $k$ then it simplifies to your problem. Note that while in the definition I said "simple paths" between parenthesis, the work cited above refers only to Directed Acyclic Graphs so that all paths are necessarily simple. Unfortunately, I am not aware of any generalization of this algorithm to Undirected (cyclic) graphs. An improvement over that paper was provided by much the same authors in Tim Schmidt, Lukas Kuhn, Bob Price, Johan de Kleer and Rong Zhou, A depth-first approach to target-value search

A different problem consists of computing the best $K$ solutions. This problem can not be solved with an A$^*$-like search algorithm because duplicate detection avoids re-expanding nodes while the second best solution might require going through the same node already considered in the best solution. One of the most influential works for this problem is David Eppstein, Finding the $k$ Shortest Paths. A recent contribution of the same problem is Husain Aljazzar, Stefan Leue, K$^*$: A heuristic search algorithm for finding the $k$ shortest paths

Now, how to combine these two problems is an unknown so that if you have any ideas ... :)

Improve this answer
$\endgroup$

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.