-3
$\begingroup$

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

$\endgroup$

closed as off-topic by Kaveh, Hsien-Chih Chang 張顯之, David Eppstein, Lev Reyzin Sep 19 '14 at 14:20

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – Lev Reyzin
  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Hsien-Chih Chang 張顯之, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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
3
$\begingroup$

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$.

$\endgroup$
  • 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.