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 :)

  • $\begingroup$ 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. $\endgroup$ – Jan Johannsen Sep 18 '14 at 14:34
  • 4
    $\begingroup$ There is a simple reduction from directed stHamPath. $\endgroup$ – Kaveh Sep 18 '14 at 16:08
  • 3
    $\begingroup$ Crossposted on CS.SE $\endgroup$ – Juho Sep 19 '14 at 7:32

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<j\leq n\}$, and $w(x_i,v_2)=0$, $w(v_1,x_j)=w(x_i,x_j)=x_j$.

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

| cite | improve this answer | |
  • 2
    $\begingroup$ 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) $\endgroup$ – Juho Sep 19 '14 at 7:33

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