<p>This is not a solution, but a reference suggestion.</p>

<p>The problem should be (a special case of the decision version of) the partially-ordered knapsack problem.  For example, you can look at the following paper and the references therein.</p>

<p>S.G. Kolliopoulos and G. Steiner: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics 155 (2007) 889-897.  <a href="http://dx.doi.org/10.1016/j.dam.2006.08.006" rel="nofollow">http://dx.doi.org/10.1016/j.dam.2006.08.006</a></p>

CC BY-SA 3.0
2011-08-25T17:54:02.370Z
Thank you very much. The partial order in that paper is the inverse of "implication" in my problem. I will take a careful look at your reference.
Peng Zhang
CC BY-SA 3.0
2011-08-25T17:35:09.440Z
2011-08-25T17:35:09.440Z
Yoshio Okamoto
<p>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.</p>

<p>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&#39;(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).</p>

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

<p>I have proved this problem as <strong><a href="http://en.wikipedia.org/wiki/Strongly_NP-complete" rel="nofollow">strongly NP-complete</a></strong> via a reduction from CLIQUE. </p>

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

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

<p><strong>Special case solved</strong>: 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$.</p>

CC BY-SA 3.0
2011-08-25T07:39:51.853Z
I don't see a question.
Kaveh
CC BY-SA 3.0
2011-08-25T07:46:09.457Z
ps: I am starting to doubt if you really care about the questions you are posting, e.g. I closed [this one](http://cstheory.stackexchange.com/questions/7710/is-counting-the-independent-sets-of-a-comparability-graph-with-maximum-degree-3) 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.
Kaveh
CC BY-SA 3.0
2011-08-25T07:46:31.717Z
@Kaveh, Peng: I modified part of the question. Does that make sense?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-08-25T07:52:52.653Z
@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.
Peng Zhang
CC BY-SA 3.0
2011-08-25T07:55:00.940Z
@Peng, that is a reasonable explanation, thanks.
Kaveh
CC BY-SA 3.0
2011-08-25T07:55:36.610Z
@Hsien-Chih Chang : Thank you very much.
Peng Zhang
CC BY-SA 3.0
2011-08-25T15:58:04.750Z
Have you tried using the obvious reduction from max-clique and the  inapproximability of max-clique to argue that your problem is also inapproximable?
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-25T16:25:16.993Z
@Artem Kaznatcheev: Sorry, I don't understand your comment? Maybe I forgot to add another constraint on my problem. The implication is not circular, i.e., $(a,b),(b,a)$ cannot be both in D.
Peng Zhang
CC BY-SA 3.0
2011-08-25T16:50:22.647Z
@Peng: (1) Do you allow (a,b), (b,c), (c,a) are all in D, which looks "circular" to me?  (2) You mention a "special case solved" but the running time is pseudo-polynomial.  Do you really allow such a running time for "solved" cases?
Yoshio Okamoto
CC BY-SA 3.0
2011-08-25T16:59:22.203Z
@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.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-25T17:13:08.320Z
@Yoshio, Artem : OK. If we represent the dependence constraints $D$ as a directed graph $G'(V',E')$, that $(a,b) \in D$ iff $(a,b) \in E'$. Then $G'$ is a DAG (acyclic digraph). Thank you very much. :)
Peng Zhang
<ds.algorithms><co.combinatorics>
Dependences imposed on Subset Sum Problem
Peng Zhang
# Dependences imposed on Subset Sum Problem

(Asked by: username_0 on 2011-08-25)

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

**Tags:** ds.algorithms, co.combinatorics
> **Comments:**
> **username_1**: I don't see a question.  
> **username_1**: ps: I am starting to doubt if you really care about the questions you are posting, e.g. I closed [this one](http://cstheory.stackexchange.com/questions/7710/is-counting-the-independent-sets-of-a-comparability-graph-with-maximum-degree-3) 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.  
> **username_2**: @Kaveh, Peng: I modified part of the question. Does that make sense?  
> **username_0**: @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.  
> **username_1**: @Peng, that is a reasonable explanation, thanks.  
> **username_0**: @Hsien-Chih Chang : Thank you very much.  
> **username_3**: Have you tried using the obvious reduction from max-clique and the  inapproximability of max-clique to argue that your problem is also inapproximable?  
> **username_0**: @Artem Kaznatcheev: Sorry, I don't understand your comment? Maybe I forgot to add another constraint on my problem. The implication is not circular, i.e., $(a,b),(b,a)$ cannot be both in D.  
> **username_4**: @Peng: (1) Do you allow (a,b), (b,c), (c,a) are all in D, which looks "circular" to me?  (2) You mention a "special case solved" but the running time is pseudo-polynomial.  Do you really allow such a running time for "solved" cases?  
> **username_3**: @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.  
> **username_0**: @Yoshio, Artem : OK. If we represent the dependence constraints $D$ as a directed graph $G'(V',E')$, that $(a,b) \in D$ iff $(a,b) \in E'$. Then $G'$ is a DAG (acyclic digraph). Thank you very much. :)  

---

## 1 answers

### Answer by username_4 on 2011-08-25. Score: 3

This is not a solution, but a reference suggestion.

The problem should be (a special case of the decision version of) the partially-ordered knapsack problem. For example, you can look at the following paper and the references therein.

S.G. Kolliopoulos and G. Steiner: Partially ordered knapsack and applications to scheduling. Discrete Applied Mathematics 155 (2007) 889-897. <http://dx.doi.org/10.1016/j.dam.2006.08.006>

> **Comments:**
> **username_0**: Thank you very much. The partial order in that paper is the inverse of "implication" in my problem. I will take a careful look at your reference.  

---

