<p>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\}$.</p>

<p><strong>Warmup question:</strong> Can this clustering algorithm be implemented efficiently for $k = 1$?</p>

<p><strong>Answer to warmup question:</strong> 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.</p>

<p><strong>Harder question:</strong> 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.</p>

CC BY-SA 3.0
2013-04-20T16:49:00.323Z
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)?
András Salamon
CC BY-SA 3.0
2013-04-20T20:28:35.057Z
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$.
jonderry
<ds.algorithms><graph-algorithms>
Fast algorithm for successively merging k-overlapping sets?
jonderry
# Fast algorithm for successively merging k-overlapping sets?

(Asked by: username_0 on 2013-04-20)

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.

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: 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)?  
> **username_0**: 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$.  

---

## 0 answers

