<p>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.</p>

<p>First, let me reformulate the second problem:</p>

<p>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|\}$ </p>

<p>This problem is known as the <strong>Target-Value search problem</strong> and was originally introduced in <a href="http://www.uwosh.edu/faculty_staff/furcyd/search_symposium_2008/schedule.html" rel="nofollow">Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleeer, Rong Zhou and Minh Do, Heuristic Search for Target-Value Path Problem</a>. 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 <a href="http://search-conference.org/index.php/Main/SOCS09program" rel="nofollow">Tim Schmidt, Lukas Kuhn, Bob Price, Johan de Kleer and Rong Zhou, A depth-first approach to target-value search</a></p>

<p>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 <a href="http://www.google.es/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;ved=0CDIQFjAA&amp;url=http%3A%2F%2Fpdf.aminer.org%2F001%2F059%2F121%2Ffinding_the_k_shortest_paths.pdf&amp;ei=JvgUUfm_L4y4hAfg_oHAAg&amp;usg=AFQjCNEsuG-9fK1d-yiXNgVzTYhZ1DkJgQ&amp;sig2=XHLRShYlFK5n3zvLLGxxlQ&amp;bvm=bv.42080656,d.ZG4" rel="nofollow">David Eppstein, Finding the $k$ Shortest Paths</a>. A recent contribution of the same problem is <a href="http://www.citeulike.org/user/ima/article/9630555" rel="nofollow">Husain Aljazzar, Stefan Leue, K$^*$: A heuristic search algorithm for finding the $k$ shortest paths</a></p>

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

CC BY-SA 3.0
2013-02-08T13:10:38.743Z
2013-02-08T13:10:38.743Z
Carlos Linares López
<p>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$.</p>

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

<hr>

<p>I just read that finding <em>one</em> $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.</p>

CC BY-SA 3.0
2013-01-31T09:08:34.353Z
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.
usul
CC BY-SA 3.0
2013-01-31T09:16:25.103Z
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.
usul
CC BY-SA 3.0
2013-01-31T10:04:08.663Z
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?
user13407
CC BY-SA 3.0
2013-01-31T17:11:26.457Z
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.
David Eppstein
CC BY-SA 3.0
2013-02-02T00:30:34.920Z
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.)
Neal Young
CC BY-SA 3.0
2013-02-02T00:31:49.160Z
On the other hand if the edge weights are integers in some polynomially bounded range, then standard dynamic programming will give you a poly-time algorithm.
Neal Young
CC BY-SA 3.0
2013-02-03T15:42:37.387Z
Yes @usul, I wanted them to be simple paths. I was trying to find feasible solutions to a shortest path problem variation I'm working on...
Arthur Araruna
CC BY-SA 3.0
2013-02-08T14:41:15.090Z
@araruna: Please edit the question to include the condition that the paths must be simple.  That condition makes a crucial difference.
Tsuyoshi Ito
<graph-theory><graph-algorithms>
Enumerating all s-t paths with cost exactly k
Arthur Araruna
# Enumerating all s-t paths with cost exactly k

(Asked by: username_0 on 2013-01-31)

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.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_2**: 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?  
> **username_3**: 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.  
> **username_4**: 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.)  
> **username_4**: On the other hand if the edge weights are integers in some polynomially bounded range, then standard dynamic programming will give you a poly-time algorithm.  
> **username_0**: Yes @usul, I wanted them to be simple paths. I was trying to find feasible solutions to a shortest path problem variation I'm working on...  
> **username_5**: @araruna: Please edit the question to include the condition that the paths must be simple.  That condition makes a crucial difference.  

---

## 1 answers

### Answer by username_6 on 2013-02-08. Score: 3

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](http://www.uwosh.edu/faculty_staff/furcyd/search_symposium_2008/schedule.html). 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](http://search-conference.org/index.php/Main/SOCS09program)

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](http://www.google.es/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CDIQFjAA&url=http%3A%2F%2Fpdf.aminer.org%2F001%2F059%2F121%2Ffinding_the_k_shortest_paths.pdf&ei=JvgUUfm_L4y4hAfg_oHAAg&usg=AFQjCNEsuG-9fK1d-yiXNgVzTYhZ1DkJgQ&sig2=XHLRShYlFK5n3zvLLGxxlQ&bvm=bv.42080656,d.ZG4). A recent contribution of the same problem is [Husain Aljazzar, Stefan Leue, K$^\*$: A heuristic search algorithm for finding the $k$ shortest paths](http://www.citeulike.org/user/ima/article/9630555)

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


---

