Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 '12 at 17:54
    
@Gerhard Paseman The variable $k$ is always some fixed small, even integer, e.g. k = 2 or k = 4. –  user27410 Oct 20 '12 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$. –  user27410 Oct 20 '12 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 '12 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 '12 at 18:43
show 6 more comments

1 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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.