# weight constrained shortest path problem variants

Given a graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:E\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{e\in E_{p}} w(e) \leq W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$, where $W,K\in Z^{+}$.

This is Weight constrained Shortest Path Problem, and known to be NP-complete for undirected as well as directed even acyclic graphs. as long as $\delta$ and $w$ is not equal for all edges. Now if we move weight from edges to vertices and change $\leq$ of total weight constraint to $=$ then the new problem is:

Given a directed acyclic graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:V\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{v\in V_{p}} w(v) = W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$.

Is this problem known ? is this solvable in P time ? or this is NP-complete too ? I think even if we replace $\mathbb{Z}^{+}$ with $\mathbb{R}^{+}$ it will not change nature of the problem.

If we set $W=\vert V \vert$ then it tries to reach all the vertices which looks like hamiltonian path problem, but it is a DAG.

## Update

I was trying to reduce it from Subset Sum as suggested by @D.W.

Given $X=\{1,2,3\}$ of size $\vert X \vert = n$ I can convert that to a graph of $n^{2}+n+2$ vertices. We can make $n$ layers of $X$ and connect every vertex with all vertices of next layer except itself. Keep a vertex with 0 weight on each layer. As show below.

But this reduction has 2 restrictions.

1. Every Layer is not complete bipartite (e.g. $2_{i}$ does not connect to $2_{i+1}$).
2. Every layer must have a vertex with 0 weight.

Now this does not prove the second problem for General purpose DAG. I can not connect $x_{i}\rightarrow x_{i+1}$ because that will change the original problem. So if there is a DAG that looks very similar to this one but have $n^{2}$ edges between each layer and have no 0 weight vertex this reduction does not apply to that graph.

Also in this formulation I can take the same element twice $1_{1}\rightarrow 2_{2}\rightarrow 1_{3}$ which will add to $4$. Which I should not be allowed

• Have you tried reducing from subset-sum? – D.W. Feb 6 '18 at 8:05
• Yes that was a typo, Thanks. The problem is with the acyclic. But if the problem is known I don't need to reduce. Also I don't think I can reduce the second one from first one. I thought I will check the proof for the first one but that is a private communication. – Neel Basu Feb 6 '18 at 9:37
• I suggest you try reducing from subset-sum. The reduction looks immediate to me, if I'm not missing something, but I'll let you check the details. – D.W. Feb 6 '18 at 13:08
• Yes I understand why it looks immediate each element will be translated to a vertex of a complete graph. The only thing I am afraid of is to prove it for DAG and remove the complete graph restriction. I am not sure how far I can go with vertex splitting to get rid of that. I will try tonight. – Neel Basu Feb 6 '18 at 15:35
• Thanks. Partial Success. But the DAG generated after reduction is not a general DAG. Please check update. – Neel Basu Feb 6 '18 at 19:22

• Definition requires P-time transformation of Input $I_{x}\rightarrow I_{y}$. Now how can I defy this argument ? if $Y$ is chain of complete bipartite graphs (with no infinite edge cost allowed) then how will that transform function generate $I_{y}$ ? – Neel Basu Feb 7 '18 at 8:19
• Also is this even correct ? because I can take the same element twice $1_{1}\rightarrow 2_{2}\rightarrow 1_{3}$ which will add to $4$. Which I should not be allowed. This may lead to a scenario when there is no such subset in the original problem but there is a path in the reduced problem. Also number of solutions not preserved. – Neel Basu Feb 7 '18 at 11:57