Dependences imposed on Subset Sum Problem

Given a set of $n$ positive integer variables, namely $S=\{ s_1, s_2, \cdots, s_n\}$. Find a subset $A \subseteq S$, so that $\Sigma_{s_i \in A} s_i = K$. $K$ is a given parameter.

Unlike the usual one, there is a dependence constraint set here, $D=\{ (a_1, b_1), \cdots, (a_m, b_m) \}$. Here $(a_i, b_i)$ means $a_i \in A$ implies $b_i \in A$. Furthermore, the dependence is not circular. Put another way, if we represent $D$ as a directed graph $G'(V, E)$, that nodes in $G$ corresponds to variable in $S$ and $(a,b) \in D$ iff $(a,b) \in E$, then $G$ is a DAG (acyclic digraph).

Note: Pseudo-polynomial time in terms of $\Sigma_{s \in S} s$ is acceptable for my problem.

I have proved this problem as strongly NP-complete via a reduction from CLIQUE.

Question. I am looking forward to an algorithm that finds a subset $A$ so that $\Sigma_{s_i \in A} s_i$ lies in a neighbourhood of $K$, e.g., between $(1-\alpha)*K$ and $(1+\alpha)*K$.

Thank you very much for your comment and answer. :) Any reference concerning is welcome.

Special case solved: When each variable is implied by at most one another variable, i.e., $\forall_{b \in S}$, $|\{(a,b) \in D \}| \le 1$, it could be solved by DP in $O(n*M*M)$. $M=\Sigma_{s_i \in S} s_i$.

• I don't see a question. Aug 25, 2011 at 7:39
• ps: I am starting to doubt if you really care about the questions you are posting, e.g. I closed this one because you simultaneously cross-posted on MO and commented that you can ask us to reopen if you don't get an answer on MO, you haven't got an answer on MO but you didn't ask us to reopen it. Aug 25, 2011 at 7:46
• @Kaveh, Peng: I modified part of the question. Does that make sense? Aug 25, 2011 at 7:46
• @Kaveh: Sorry for your doubt. If you look at questions I posted (excepted the closed two), actually I partitioned a lot in the comments other users gave to me. The problem you mentioned, although no answer has shown up at MO, it cause two ups. So I am watching the status of MO, all the time. Aug 25, 2011 at 7:52
• @Peng could you please take the time to spell out ALL your constraints clearly in the question before we waste time thinking about it, because I don't see anything in the previous versions of this question that even hinted at this non-circularity constraint. Aug 25, 2011 at 16:59