Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
