Finding largest closest subsets

Question

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.

Answer 1

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.