Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to find the largest common subset across the largest subset of $S$.

For example:

$S = \{~\{1, 5, 4\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$ has $\{4\}$ in common across all subsets.

$T = \{~\{1, 2, 6\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$ has $\{3, 4\}$ in common across the subset $\{T_1, T_2\}$


I understand the problem to be the following:

Given sets $A_1,\dots,A_n$, find the largest $k$ such that there exist $k$ distinct indices $i_1,\dots,i_k$ that make $A_{i_1} \cap \cdots \cap A_{i_k}$ have a non-empty intersection.

This can be solved in $O(nm)$ time, where $m$ denotes the maximum size of any of the $A_i$. It suffices to find $x$ in $A_1 \cup \cdots \cup A_n$ that maximizes $|\{i : x \in A_i\}|$ (i.e., the number of sets $A_1,\dots,A_n$ that contain $x$). When you've found this $x$, you can output the corresponding set $\{i : x \in A_i\}$ of indices. You can output the intersection $\cap_{i : x \in A_i} A_i$ too if you want.

Naively, this might appear to take $O(n^2m)$ time. However, the algorithm can be implemented in $O(nm)$ time, by scanning through the elements of the sets, maintaining a hashtable with a counter for each element $x$ that counts the number of sets it is contained in, and incrementing the right counter as you encounter each element.

The correctness follows from the fact that if $A_{i_1} \cap \cdots \cap A_{i_k}$ has a non-empty intersection, there must be some $x \in A_1 \cup \cdots \cup A_n$ that is contained in $A_{i_1} \cap \cdots \cap A_{i_k}$, and thus the algorithm above will find that combination of indices.


Your Answer

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

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