Let $I$ be a finite set of items and $\mathcal{M} = \{M | M \subseteq I\}$ be a set of subsets of $I$.
The task is to find the biggest subset $\tilde{\mathcal{M}} \subseteq \mathcal{M}$ so that all elements of $\tilde{\mathcal{M}}$ are pairwise disjoint:
$$\text{arg } \max_{\tilde{\mathcal{M}} \subseteq \mathcal{M}} |\tilde{\mathcal{M}}| \text{ with } \bigcap_{M \in \tilde{\mathcal{M}}} M = \emptyset$$
What is an efficient algorithm to do so?
(If $|I| \approx 10\,000$ and $|\mathcal{M}| \approx 100$ )
Example
Let $I = \{a, b, c, d, e\}$ be the set of items and
$$\mathcal{M} = \{A, B, C, D\}$$
with
$$ \begin{align} A &= \{a\}\\ B &= \{b, c\}\\ C &= \{a, c\}\\ D &= \{b, d\} \end{align} $$
Then $$\tilde{\mathcal{M}} = \{A, B\}$$ is one of the solutions. There is no way to have $|\tilde{\mathcal{M}}| \geq 3$.
Ideas
Brute force
M_tilde_max = None
for Mc_tilde in powerset(Mc):
if Mc_tilde is disjunct and (M_tilde_max is None or M_tilde_max < |Mc_tilde|):
M_tilde_max = Mc_tilde
This has complexity $\mathcal{O}(2^{|\mathcal{M}|})$.
Apriori
If a set $\tilde{\mathcal{M}}$ has only disjunct items, then all possible subsets have to be disjunct. So one can at first find all sets of size 1 which have this property (which are simply all sets), then all sets of size two, then all of size 3, ...
This has the same worst-case time complexity as brute force as in the worst case $\tilde{\mathcal{M}}$ is just equal to $\mathcal{M}$. It might in some scenarios - if one knows that it will be smaller - be much better. However, the space complexity is quite bad here.
More
I guess one could pre-compute for all $|\mathcal{M}|^2$ combinations of two sets if they are disjunct or not. After that, the table can be used and $\mathcal{M}$ and $I$ don't have to be touched at all. This is the maximum satisfiability problem. Each set $M_i \in \mathcal{M}$ is a boolean variable $x_i$. If $M_i$ and $M_j$ are disjunct, then $(x_i \lor x_j)$ is added. If not, then either $(x_i \lor \neg x_j)$ or $(\neg x_i \lor x_j)$ can be added (I think it doesn't matter which one?). This way, a conjunctive normal form can be produced. All clauses have only two elements, so I think there might be an efficient algorithm for it?
Context
This question is more a brain-teaser for me. It started with the following problem:
I would like to generate a tree of categories for Wikimedia commons. The problem is that categories in Wikimedia Commons are not disjunct. For example, for https://commons.wikimedia.org/wiki/Category:Rosa there is the category "Roses by location", "Rosa by month", "Roses by photographer" which are not what I want. However, to filter those I think just removing categories with the substring " by " might be enough. I have to check it, though.
