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

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

<p>Construct an instance of your problem as follows:</p>

<ul>
<li><p>Our "alphabet" is $A = V \cup \{ 0,1,\dotsc,k-1 \}$.</p></li>
<li><p>The sets $s_i$ are indexed with $i \in I = E \cup \{ \bot \}$.</p></li>
<li><p>For each $e = \{u,v\} \in E$ we have $s_e = \{ 1,2,\dotsc,k-1, u, v\}$.</p></li>
<li><p>We also define $s_\bot = \{ 0,1,\dotsc,k-1 \}$.</p></li>
</ul>

<p>Observations:</p>

<ul>
<li><p>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$.</p></li>
<li><p>There cannot be a solution of size $2k+1$ or larger: it would imply $|s \cap s_\bot| &gt; k = |s_\bot|$, a contradiction.</p></li>
<li><p>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$.</p></li>
</ul>

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

<ul>
<li><p>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$.</p></li>
<li><p>Conversely, if we have a vertex cover of size $k$, we can construct a solution of size $2k$.</p></li>
</ul>

<p>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 &lt; p &lt; 1$.</p>

<hr>

<p><strong>Edit:</strong> 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.</p>

<p>However, this does not seem to be the case. It seems that it is actually NP-hard to find <em>any non-trivial solution</em> (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.</p>

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

CC BY-SA 3.0
2011-10-14T11:43:34.100Z
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.
Andras Hajdu
CC BY-SA 3.0
2011-10-14T11:43:53.723Z
We also check different search algorithms to find the s sets, but cannot see cleraly the approximation rates.
Andras Hajdu
CC BY-SA 3.0
2011-10-14T16:48:18.530Z
@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.
Suresh Venkat
CC BY-SA 3.0
2011-10-14T18:24:43.237Z
@Suresh Venkat OK, I did it so, the new constraint is added in a new question.
Andras Hajdu
CC BY-SA 3.0
2011-10-15T13:49:39.883Z
@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$.
Jukka Suomela
CC BY-SA 3.0
2011-10-10T00:18:47.720Z
2011-10-10T07:56:39.527Z
2011-10-10T07:56:39.527Z
Jukka Suomela
<p><strong>Original question:</strong></p>

<p><em>Base problem:</em> 
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 </p>

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

<p>ii) $|s|$ is maximal. </p>

<p><em>First variant:</em> 
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 </p>

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

<p>ii) $|\{j : |c_j \cap s| \ge p|s|\}| \le q&#39;M$, where $p,q&#39;\in [0,1]$ is fixed. </p>

<p>iii) $|s|$ is maximal. </p>

<p><em>Interpretation for better understanding:</em> 
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&#39;*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. </p>

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

<hr>

<p><strong>Question 2 (new constraint added):</strong></p>

<p>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:</p>

<p><em>In Base problem:</em></p>

<p>iii) $|s| &lt; |s_i|$, for all $i=1,...,N$. </p>

<p><em>In First variant:</em></p>

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

<p>The questions regarding the problems remain the same.</p>

<p><em>Interpretation for better understanding of this new size constraint:</em>
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. </p>

CC BY-SA 3.0
2011-10-09T12:15:22.047Z
The notation is hard to follow.  What does “s \cap t” mean when s and t are strings?
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-09T16:02:59.783Z
It's not very clear to me whether you need $s$ to be a subsequence or a substring.
zotachidil
CC BY-SA 3.0
2011-10-09T18:00:13.197Z
Tsuyoshi Ito: \cap stands for set intersection (since s and t are considered as sets) azotlichid: the problem is formulated for strings, but since letters are different within the words now s can be interpreted as a subsequence (or simply subset). The problem could have been formulated with sets, so it looks a bit simpler than string problems.
Andras Hajdu
CC BY-SA 3.0
2011-10-09T18:23:58.810Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-09T18:25:56.840Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-09T20:42:24.357Z
I think it would be helpful to re-formulate your problem so that you refer to sets, not strings.
Jukka Suomela
CC BY-SA 3.0
2011-10-10T00:35:16.160Z
@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.
Suresh Venkat
CC BY-SA 3.0
2011-10-14T11:38:38.973Z
@All Thanks for your responses. I formulated the problem for sets and added a new size constraint for the desired s sets. This constraint is completely reasonable from practical point of view.
Andras Hajdu
<ds.algorithms><co.combinatorics><approximation-algorithms>
Finding largest closest subsets
Andras Hajdu
# Finding largest closest subsets

(Asked by: username_0 on 2011-10-09)

**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.

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms
> **Comments:**
> **username_1**: The notation is hard to follow.  What does “s \cap t” mean when s and t are strings?  
> **username_2**: It's not very clear to me whether you need $s$ to be a subsequence or a substring.  
> **username_0**: Tsuyoshi Ito: \cap stands for set intersection (since s and t are considered as sets) azotlichid: the problem is formulated for strings, but since letters are different within the words now s can be interpreted as a subsequence (or simply subset). The problem could have been formulated with sets, so it looks a bit simpler than string problems.  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_3**: I think it would be helpful to re-formulate your problem so that you refer to sets, not strings.  
> **username_4**: @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.  
> **username_0**: @All Thanks for your responses. I formulated the problem for sets and added a new size constraint for the desired s sets. This constraint is completely reasonable from practical point of view.  

---

## 1 answers

### Answer by username_3 on 2011-10-10. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: We also check different search algorithms to find the s sets, but cannot see cleraly the approximation rates.  
> **username_4**: @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.  
> **username_0**: @Suresh Venkat OK, I did it so, the new constraint is added in a new question.  
> **username_3**: @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$.  

---

