5
$\begingroup$

Consider the following algorithm for clustering sets: Begin with $n$ sets, $S_1, S_2, \ldots,S_n$, such that $$\sum_{i = 1}^n |S_i| = m \,,$$ and successively merge sets with at least $k$ elements in common. E.g., if $S_1 = \{1, 2, 3\}$, $S_2 = \{3, 4, 5\}$, and $S_3 = \{5, 6, 7\}$, and $k = 1$, then $S_1$ can be merged with $S_2$ to create $S_1' = \{1, 2, 3, 4, 5\}$, and $S_1'$ can be merged with $S_3$ to create $S_1'' = \{1,\ldots,7\}$.

Warmup question: Can this clustering algorithm be implemented efficiently for $k = 1$?

Answer to warmup question: If the sets only need to overlap by one element to be merged as in the example above, the clustering can be performed in $O(m)$ time using connected components if you are careful.

Harder question: Suppose the sets must overlap by at least 2 (or $k$) elements to be merged. Is there an efficient algorithm for this case (i.e., close to linear time)? The challenge here is that you can have cases like $S_1 = \{1, 2, 3\}$, $S_2 = \{2, 4, 5\}$, $S_3 = \{1, 4, 5\}$, with $k = 2$. Note that in this case $S_1$ can be merged with $S_2$ and $S_3$, but only after $S_2$ and $S_3$ are merged to create $S_2'$ so that $S_1$ and $S_2'$ share both elements 1 and 2.

$\endgroup$
  • $\begingroup$ Do you have any reason to expect better than $O(m^k)$ time? Also, are you more interested in the dependence on $n$, on $m$, or some other parameter (such as the maximum number of sets any element belongs to)? $\endgroup$ – András Salamon Apr 20 '13 at 16:49
  • $\begingroup$ A naive algorithm is to compute the intersection of all sets, and merge two sets if you find a pair that share $k$ elements, and repeat until no two sets share $k$ elements. This has a running time of $O(m^2)$ per iteration, with at most $O(n)$ iterations (no dependence on $k$). I'm interested if this can be done in close to linear time, even for $k = 2$. $\endgroup$ – jonderry Apr 20 '13 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.