2
$\begingroup$

Original question:

Base problem: Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose subsets $s_i$ ($i=1,...,N$) from $A$. Elements cannot be repeated within any sets, e.g. $|s_i \cap A| = |s_i|$, where $|.|$ stands for set cardinality. The cardinalities of sets $s_i$ may differ. The problem is to find sets $s$ composed from $A$ so that

i) $|s_i \cap s| \ge p|s|$, for all $i=1,...,N$, where $p\in [0,1]$ is fixed.

ii) $|s|$ is maximal.

First variant: Let $A\subset \mathbb{N}$ be a finite set with elements $a_k$, ($k=1,...,L$). We compose sets $s_i$ ($i=1,...,N$) from $A$ so that $|s_i \cap A| = |s_i|$, that is, an $s_i$ set contains different elements. We also compose sets $c_j$ ($j=1,...,M$) from $A$ so that $|c_j \cap A| = |c_j|$, that is, a subset $c_j$ contains different elements. The cardinalities of the sets $c_j$ may differ. The problem is to find sets $s$ composed from $A$ so that

i) $|\{i : |s_i \cap s| \ge p|s|\}| \ge qN$, where $p,q\in [0,1]$ is fixed.

ii) $|\{j : |c_j \cap s| \ge p|s|\}| \le q'M$, where $p,q'\in [0,1]$ is fixed.

iii) $|s|$ is maximal.

Interpretation for better understanding: The $a_k$ elements are different mutations that we can represent e.g. with different natural numbers. We have samples for two populations, $\{s_i\}$ are the diseased persons, $\{c_j\}$ are the average ones, and we know that $q'*100\%$ is the presence of the disease on average. We want to find characteristic mutation patterns (sets $s$) that are characteristic for the diseased (at least $q*100\%$) but less characteristic (only up to $q'*100\%$) for the average population. We say that $s$ is characteristic if at least its $p*100\%$ portion appears in a diseased person.

We would need known theoretical results, complexity of the algorithm and algorithmic approaches for the search.


Question 2 (new constraint added):

Jukka Suomela has given a correct answer for the Base problem in the Original question. Regarding his answer and also since from practical point of view it is reasonable, an extra constraint can be added to the problem as:

In Base problem:

iii) $|s| < |s_i|$, for all $i=1,...,N$.

In First variant:

iv) $|s| < r|s_i|$, for all $i=1,...,N$, where $r\in [0,1]$ is fixed.

The questions regarding the problems remain the same.

Interpretation for better understanding of this new size constraint: We can estimate the number of mutations for a person to be approx. 1 million (that is, $|s_i|,|c_i| \approx 10^6$), while disease-sepcific mutation patterns are expected to be much smaller (say $|s|\approx 50$, but we do not know). This is the reason for the size constraints for $s$ in the problem.

$\endgroup$
  • $\begingroup$ The notation is hard to follow. What does “s \cap t” mean when s and t are strings? $\endgroup$ – Tsuyoshi Ito Oct 9 '11 at 12:15
  • 1
    $\begingroup$ You should edit your own question, but you cannot because you are using two different unregistered accounts. Please register an account and ask moderators to merge your two unregistered accounts (6824 and 6826) to your registered account. $\endgroup$ – Tsuyoshi Ito Oct 9 '11 at 18:23
  • 1
    $\begingroup$ As for your reply, you wrote “since s and t are considered as sets” as if it were an obvious thing, but do not assume that everyone understands your own convention. $\endgroup$ – Tsuyoshi Ito Oct 9 '11 at 18:25
  • 2
    $\begingroup$ I think it would be helpful to re-formulate your problem so that you refer to sets, not strings. $\endgroup$ – Jukka Suomela Oct 9 '11 at 20:42
  • 1
    $\begingroup$ @AndrasHajdu please flag your question with a request for merging the two accounts. It looks like this needs to be done, but it would be better if the request came from you. $\endgroup$ – Suresh Venkat Oct 10 '11 at 0:35
2
$\begingroup$

Let us consider your "base problem" and the special case of $p = 1/2$.

Assume that we are given a graph $G = (V,E)$ and a positive integer $k \le |V|$.

Construct an instance of your problem as follows:

  • Our "alphabet" is $A = V \cup \{ 0,1,\dotsc,k-1 \}$.

  • The sets $s_i$ are indexed with $i \in I = E \cup \{ \bot \}$.

  • For each $e = \{u,v\} \in E$ we have $s_e = \{ 1,2,\dotsc,k-1, u, v\}$.

  • We also define $s_\bot = \{ 0,1,\dotsc,k-1 \}$.

Observations:

  • There is a trivial solution $s$ of size $2k-2$: just take a subset $s \subseteq A$ with $\{1,2,\dotsc,k-1\} \in s$ and $|s| = 2k-2$. Clearly $|s \cap s_i| \ge k-1$ for all $i$.

  • There cannot be a solution of size $2k+1$ or larger: it would imply $|s \cap s_\bot| > k = |s_\bot|$, a contradiction.

  • If there is a solution $s$ of size $2k-1$, we can pad it with an arbitrary element to obtain a solution of size $2k$.

Hence the key question is whether there exists a solution $s$ of size $2k$.

  • Assume that we have a solution $s$ of size $2k$. Then $s_\bot = \{0,1,\dotsc,k-1\} \subseteq s$. Hence $s = \{0,1,\dotsc,k-1\} \cup X$, where $X \subseteq V$ and $|X| = k$. Moreover, if $e = \{u,v\} \in E$, we must have $|s \cap s_e| \ge k$, which implies $e \cap X \ne \emptyset$. That is, $X$ is a vertex cover of size $k$.

  • Conversely, if we have a vertex cover of size $k$, we can construct a solution of size $2k$.

Hence it is NP-hard to find an optimal $s$. The same idea can be used to show that the problem is hard for any $0 < p < 1$.


Edit: Now a natural question is whether there is an approximation algorithm – for example, can one always find a feasible solution $s$ that is within a constant factor of the largest feasible solution.

However, this does not seem to be the case. It seems that it is actually NP-hard to find any non-trivial solution (i.e., a solution $s \ne \emptyset$), at least for certain values of $p$. The construction is a bit messy, though, but I can try to work out the details if needed.

Anyhow, it seems that to get anything positive (with provable performance guarantees), you need to relax your constraints a bit.

$\endgroup$
  • $\begingroup$ Dear Jukka, as we see your counter-example is indeed correct. However, I added a new condition iii) which requires that s should not be larger than the s_i sets. It is a natural constraint as the s_i sets contain approx. 1 million elements while the characteristic pattern s is expected to be much-much smaller (e.g 50). I just hope that this size constraint may help a bit, since in your construction |s| is much larger than the |s_i|'s which is actually the reversed logic. If you switch the roles: s<->s_i, perhaps your example remains valid, but we are not convinced ourselves yet. $\endgroup$ – Andras Hajdu Oct 14 '11 at 11:43
  • $\begingroup$ We also check different search algorithms to find the s sets, but cannot see cleraly the approximation rates. $\endgroup$ – Andras Hajdu Oct 14 '11 at 11:43
  • $\begingroup$ @AndrasHajdu it's generally recommended that you not change the original question based on answers given by others. In this case, I'd recommend you clean up everything above the line in the question, and add the new constraint as a secondary question below the first one, mentioning that Jukka's answer addresses the first one. $\endgroup$ – Suresh Venkat Oct 14 '11 at 16:48
  • 1
    $\begingroup$ @Suresh Venkat OK, I did it so, the new constraint is added in a new question. $\endgroup$ – Andras Hajdu Oct 14 '11 at 18:24
  • $\begingroup$ @AndrasHajdu: Regarding the new constraint: can't you simply add some "padding" to each $s_i$ to make sure that $|s| < |s_i|$? For example, in the above construction, let $P = I \times \{1,2,...,t\}$ be the set of "padding" elements. Add $P$ to $A$, and then for each $i \in I$ add $\{(i,1),(i,2),...,(i,t)\}$ to $s_i$. Then we have increased the size of each $s_i$ by $t$. But it does not really change the structure of feasible solutions. Informally, it never makes sense to add any padding element $p \in P$ to $s$. $\endgroup$ – Jukka Suomela Oct 15 '11 at 13:49

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.