Provided a list of sets, $L$, computing an array where each entry $q_i \in Q$ is the family of sets in $L$ that have intersection $k$ with $l_i \in L$

Question

I have a set of $(l_1, ..., l_N) \in L$ smaller sets, each with $(r_1, ..., r_M) \in R$ integer elements. I would like create an ordered array of $(q_1, ..., q_N) \in Q$ sets s.t.:

(1) Each $q_i \in Q$ consists of an unordered list of all such $(l_a, ..., l_b) \in L$ with an intersection of size $k$ with $l_i$ - i.e. where $||l_i \cap l_a|| = k, ||l_i \cap l_{a+1}|| = k, ..., ||l_i \cap l_b|| = k$.

(2) If $i$ and $j$ are successive integers, i.e. $j = (i + 1)$, then we have that $q_i \cap q_j \geq 1$

---

If we are guaranteed upper and lower bounds on the number of elements in each $q_i \in Q$, what is an optimal algorithm for generating the ordered array $Q$? What might be its worst-case time and space complexity, or its average time and space complexity?

---

Here's an example to help illustrate what I'm trying to do...

Take $L =$ {{1, 2, 3, 4}, {1, 3, 1510, 28897}, {1, 12, 557, 204}, {1, 3, 1510, 28897}}

$l_1 =$ {1, 2, 3, 4}; $l_2 =$ {1, 3, 1510, 28897}; $l_3 =$ {1, 12, 557, 204}; $l_4 =$ {1, 3, 1510, 28897}

To generate $q_1$ for $k = 2$, we note that the set $l_1$ has an intersection of size $k = 2$ with $l_2$, an intersection of size $1$ with $l_3$, and an intersection of size $2$ with $l_4$. So we write $q_1 =$ {2, 4}. Likewise, we can write $q_2 =$ {1}, $q_3 =$ {}, and $q_4 =$ {1}. The set of all $q_i$ sets is the set $Q$.

Answer 1

Probably the optimization that you want to take is the following: if j > i and j is in q_i, then i is going to be in q_j. Here I assume the q_i are sets of indices, and that j is in q_i precisely when l_i intersect l_j has size exactly k.

Beyond that, I see no optimization one can take in the general case, given that k is fixed in advance. There may be some special cases, for example when l_i has less than k elements, you can skip processing of it. Also, if there is a special order, say you know some l's are subsets of others, then you can do some speedup.

In general though, things won't be much faster than, for all i and j with i < j, computing l_i intersect l_j and determining if that intersection has the right size.

Now if the goal is to find a value of k such that q_i cap q_{i+1} is nonempty for all i, that may take a little longer, but there won't be that many distinct values of k to check.

Gerhard "Ask Me About System Design" Paseman, 2012.10.21