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

$\endgroup$
  • 1
    $\begingroup$ You need to formalise the restriction "but with a specific weight"; as stated, there's a trivial reduction from Hamiltonian Cycle (all weights $1$, $w=n$, $v_1=v_2$). Idea: edge weight should be pairwise distinct. (Then, see FrankW's answer.) $\endgroup$ – Raphael Sep 18 '14 at 16:03
2
$\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) \mid i\in [n]\}\cup \{(x_i,v_2) \mid i\in [n]\}\cup \{(x_i,x_j) \mid 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$
  • 1
    $\begingroup$ I can understand the reduction, but i don't yet see the 'trivial' part, i.e. $\in$ NP. I mean, i could provide a path with an exponential number of edges and surely this can not be verified in P-Time w.r.t the size of the graph? $\endgroup$ – Tyler Durden Sep 19 '14 at 15:59
  • $\begingroup$ Showing it's in NP is simple enough, "guess" the path and verify it by summing the edge weights. If you're concerned about the length of the path (which indeed might have to be exponential in the representation of the target T), no worries- such path would have to go over some cycles exponential number of times, then simply allow the guessing part to encode how many times the path goes over a loop in binary. $\endgroup$ – R B Sep 19 '14 at 16:15
  • $\begingroup$ Ok i see, so if you could answer a general NP question that would be great: given a non-deterministic turing machine $M$ that recognises the language, the input is only the guess : $x$, and not the whole graph, so it really doesn't matter what the size of $x$ is, only that the $M$ can verify $x$ in time $p(|x|)$ w.r.t some polynomial $p$? $\endgroup$ – Tyler Durden Sep 19 '14 at 17:17
  • $\begingroup$ The guessed part (the path in our case) needs to be of polynomial length in the size of the graph- but this is indeed the case when you encode the number of times the graph goes over some loop in binary. $\endgroup$ – R B Sep 19 '14 at 17:38
  • 2
    $\begingroup$ @RB a small latex tip: \mid is usually a better choice than | because it makes the spacing look nicer :-) $\endgroup$ – Juho Sep 20 '14 at 6:47
4
$\begingroup$

This problem is NP-complete.

The "$\in$ NP"-part is trivial.

For the NP-hard part we reduce directed hamiltonian path:

Given a directed graph $G=(V,E)$ and two vertices $v_1,v_2\in V$, is there a path from $v_1$ to $v_2$, that visits each vertex exactly once?

For the reduction we keep $G$, $v_1$, and $v_2$ and number the nodes from $1$ to $n$, so that $v_2$ gets the number $n$. Then we assign each edge from node $i$ to node $j$ the weight $2^n+2^i$ and ask for a path of weight $n\cdot 2^n-1$.

It is easy to compute, that a hamiltonian path will have the correct weight.

For the other direction note that any path that takes $n$ steps or more would have a weight above $n\cdot 2^n$ and thus be invalid. A path that only takes $n-2$ or fewer steps on the other hand would have a weight below $(n-1)\cdot 2^n$, which is also invalid. So any valid path will have a length of $n-1$.

Furthermore the required weight has the bit for $2^i$ set to $1$ for each $0<i<n$. In order to achieve this without visiting node $i$, we would need to visit node $i-1$ (or a node with a smaller number) multiple times. But we only have $n-1$ steps to set $n-1$ bits. So only hamiltonian paths can achieve the correct weight.

The reduction works in polynomial time, since the size of the binary encoding of the weights and target is linear in the number of nodes.

$\endgroup$
  • 2
    $\begingroup$ My proof shows, that the problem is NP-complete, even if you only allow only simple graphs with positive edge weights. Allowing more graphs will not make it easier. $\endgroup$ – FrankW Sep 18 '14 at 16:05
  • $\begingroup$ If the edge weights are all positive as well as the Graph is a DAG, in that limited case, is there an Algorithm (which ?), or the same proof still applies. $\endgroup$ – TheoryQuest1 Jul 4 '16 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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