Is DAG subset sum approximable?

Question

We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$.

The DAG subset sum problem (might exist under a different name, a reference will be great) asks whether there are vertices $v_1,v_2,...,v_k$, such that $\Sigma_{v_i}g(v_i) = T$, and $v_1\to..\to v_k$ is a path in $G$.

This problem is trivially NP-Complete, as the complete transitive graph yields the classical subset sum problem.

An approximation algorithm for the DAG subset sum problem is an algorithm with the following properties:

1. If there exists a path with sum T, the algorithm return TRUE.
2. If there is no path summing up to a number between $(1 − c)T$ and $T$ for some $c\in (0,1)$, the algorithm return FALSE.
3. If there is a path summing to a number between $(1 − c)T$ and $T$, the algorithm may output any answer.

Subset sum is known to be approximable in polynomial time for all $c>0$.

Does the same hold for DAG-Subset-Sum?

Answer 1

It seems to me the pseudo-polynomial time dynamic programming algorithm for Subset Sum problem also works for this problem. For each vertex $v_i$, we compute the set $L_i$ consisting of all possible values of paths ended at $v_i$. Then, we have the recurrence relation: $L_i=\{g(v_i)\}\cup\{x+g(v_i)\mid x\in \bigcup_{j\in prec(i)} L_j\}$. Following a topological order, all the $L_i$ can be computed in $O(Km)$ time, where $K$ is the total weight and $m$ is the number of edges.

I think the standard scaling-and-rounding can also be applied to derive a FPTAS.