What is an efficient way to calculate the biggest system of disjunct sets? 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 &amp;= \{a\}\\
B &amp;= \{b, c\}\\
C &amp;= \{a, c\}\\
D &amp;= \{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 &lt; |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.
This answer assumes that the sets in $\tilde{\mathcal{M}}$ have to be pairwise disjoint (as currently stated, you are requiring them to have empty intersection, which is a monotone condition).

The decision version of your problem is NP-complete, by reduction from independent set. Given an graph $G = (V,E)$, construct a set system with a set $S_x$ for each vertex $x \in V$, and an element $e$ for each edge $e \in E$. The set $S_x$ contains all edges incident to $x$. A family of sets is pairwise disjoint iff the corresponding vertices form an independent set.

We can also go in the other direction, following one of your suggestions. Given a set system, construct a graph in which each vertex corresponds to a set, and two vertices are connected if the sets intersect. A solution to your problem is the same as an independent set in the graph.