MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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$

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

-
 Is there any relation between k and the i in q_i? If not, then there is likely an O(M^3) or better algorithm where M is the total number of sets l_i . Also, I feel there are some constraints missing which would make the problem more interesting. Gerhard "Maybe I Don't Understand It" Paseman, 2012.10.20 – Gerhard Paseman Oct 20 at 17:54 @Gerhard Paseman The variable $k$ is always some fixed small, even integer, e.g. k = 2 or k = 4. – unknown (yahoo) Oct 20 at 18:20 @Gerhard Paseman I would guess the algorithm is worst-case $O(M^2)$ since, for every set $l_i \in L$, you can scan through all $||L||$ sets and add the number of each set satisfying $||l_i \cap l_j|| = k$ to $q_i \in Q$. – unknown (yahoo) Oct 20 at 18:25 Indeed. When I am not clear on a problem, I usually add to an exponent and hedge. While you might find an O(MlogM) solution, I am still unclear on the problem to provide much insight. The basic problem is I am unsure if l_i is a number or a set. If you want me to play more, you may need to post a kilobyte or so worth of a worked out example. Gerhard "Likes To Understand Through Examples" Paseman, 2012.10.20 – Gerhard Paseman Oct 20 at 18:37 Oh. Something just clicked. You are hoping that there is (for each i) a set l_f(i) that has a nice intersection with both l_i and l_{i+1}? And further, that the sequence of f(i) will yield a nice pattern of sizes of intersections? In that case, I am concerned that there may be no known polytime solution. Gerhard "May Not Need Examples Now" Paseman, 2012.10.20 – Gerhard Paseman Oct 20 at 18:43

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.