<p>This problem is NP-complete.</p>

<p>A reduction from subset sum:</p>

<p>Given numbers $\{x_1,\ldots,x_n\}$ and a target number $T$, construct the complete transitive acyclic graph $G=(\{x_1,\ldots,x_n\}\cup \{v_1,v_2\}, E)$,</p>

<p>Where $E=\{(v_1,x_i)|i\in [n]\}\cup \{(x_i,v_2)|i\in [n]\}\cup \{(x_i,x_j)|1\leq i&lt;j\leq n\}$, and $w(x_i,v_2)=0$, $w(v_1,x_j)=w(x_i,x_j)=x_j$.</p>

<p>Now simply ask if there exists a $v_1\leadsto v_2$ path of weight $T$.</p>

CC BY-SA 3.0
2014-09-19T07:33:41.303Z
The question is likely to be closed here, and thus deleted at some point. Maybe you could add your answer on CS.SE? (see my comment to the question for the link)
Juho
CC BY-SA 3.0
2014-09-18T15:27:03.590Z
2014-09-18T19:51:31.250Z
2014-09-18T19:51:31.250Z
R B
<p>I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic.</p>

<p>The question is: given 2 nodes $v_1$ and $v_2$, is there a path from $v_1$ to $v_2$ with a weight $w$. </p>

<p>I would like to know if there are any known complexity results for this problem, or even anything related to this <strong>but</strong> with a specific weight, and not just shortest path, longest path etc. I have been thinking of representing the problem as in-equations in some type of linear programming, but before I start I'd like to get as much info as possible :)</p>

CC BY-SA 3.0
2014-09-18T14:34:36.697Z
This is not a research-level question, there are standard algorithms for this problem that can be found in most algorithm textbooks. Thus the question is off-topic here. Try asking on cs.stackexchange.com instead.
Jan Johannsen
CC BY-SA 3.0
2014-09-18T16:08:38.220Z
There is a simple reduction from directed stHamPath.
Kaveh
CC BY-SA 3.0
2014-09-19T07:32:28.303Z
[Crossposted on CS.SE](http://cs.stackexchange.com/q/30106/472)
Juho
<cc.complexity-theory><graph-theory><graph-algorithms>
Finding an exactly weighted st-path in a digraph
Tyler Durden
# Finding an exactly weighted st-path in a digraph

(Asked by: username_0 on 2014-09-18)

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic.

The question is: given 2 nodes $v\_1$ and $v\_2$, is there a path from $v\_1$ to $v\_2$ with a weight $w$.

I would like to know if there are any known complexity results for this problem, or even anything related to this **but** with a specific weight, and not just shortest path, longest path etc. I have been thinking of representing the problem as in-equations in some type of linear programming, but before I start I'd like to get as much info as possible :)

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: This is not a research-level question, there are standard algorithms for this problem that can be found in most algorithm textbooks. Thus the question is off-topic here. Try asking on cs.stackexchange.com instead.  
> **username_2**: There is a simple reduction from directed stHamPath.  
> **username_3**: [Crossposted on CS.SE](http://cs.stackexchange.com/q/30106/472)  

---

## 1 answers

### Answer by username_4 on 2014-09-18. Score: 3

This problem is NP-complete.

A reduction from subset sum:

Given numbers $\{x\_1,\ldots,x\_n\}$ and a target number $T$, construct the complete transitive acyclic graph $G=(\{x\_1,\ldots,x\_n\}\cup \{v\_1,v\_2\}, E)$,

Where $E=\{(v\_1,x\_i)|i\in [n]\}\cup \{(x\_i,v\_2)|i\in [n]\}\cup \{(x\_i,x\_j)|1\leq i

Now simply ask if there exists a $v\_1\leadsto v\_2$ path of weight $T$.

> **Comments:**
> **username_3**: The question is likely to be closed here, and thus deleted at some point. Maybe you could add your answer on CS.SE? (see my comment to the question for the link)  

---

