13
$\begingroup$

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?

$\endgroup$
14
$\begingroup$

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.

$\endgroup$

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.