<p>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.</p>

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

CC BY-SA 3.0
2014-02-18T16:44:12.523Z
2014-02-19T00:32:00.953Z
2014-02-19T00:32:00.953Z
Bangye
<p>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}$.</p>

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

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

<p>An approximation algorithm for the DAG subset sum problem is an algorithm with the following properties:</p>

<ol>
<li>If there exists a path with sum T, the algorithm return TRUE.</li>
<li>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.</li>
<li>If there is a path summing to a number between $(1 − c)T$ and $T$, the algorithm may output any answer.</li>
</ol>

<p><a href="http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm" rel="nofollow">Subset sum is known to be approximable in polynomial time for all $c&gt;0$.</a></p>

<p><strong>Does the same hold for DAG-Subset-Sum?</strong></p>

<ds.algorithms><graph-theory><graph-algorithms><approximation-algorithms><subset-sum>
Is DAG subset sum approximable?
R B
# Is DAG subset sum approximable?

(Asked by: username_0 on 2014-02-18)

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$.](http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm)

**Does the same hold for DAG-Subset-Sum?**

**Tags:** ds.algorithms, graph-theory, graph-algorithms, approximation-algorithms, subset-sum


---

## 1 answers

### Answer by username_1 on 2014-02-18. Score: 14 | Accepted answer

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.


---

