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$.
Dependences imposed on Subset Sum Problem
ds.algorithms;co.combinatorics