weight constrained shortest path problem variants

Question

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

Answer 1

Check the definition of reduction again. A reduction that works for general dags is a perfectly valid reduction. It meets all of the conditions in the definition. I suggest working through the definition -- that should help you see what is going on.

Or, to put it another way: The problem for "general DAG" is at least as hard as the problem for "a particular type of DAG", so if you've proved the problem is NP-hard for a particular type of DAG, you've also proven it is NP-hard for general DAGs, too.