# 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 &= \{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.

• Your problem statement is wrong. You want $\tilde{\mathcal{M}}$ to be pairwise disjoint. As stated, the problem is easy to solve – take $\tilde{\mathcal{M}} = \mathcal{M}$ if possible, and otherwise there is no solution other than $\tilde{\mathcal{M}} = \emptyset$. – Yuval Filmus Aug 20 '16 at 22:14
• @YuvalFilmus Have a look at the example – Martin Thoma Aug 21 '16 at 4:54

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.