1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Aug 20 '16 at 22:14
  • $\begingroup$ @YuvalFilmus Have a look at the example $\endgroup$ – Martin Thoma Aug 21 '16 at 4:54
4
$\begingroup$

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.

$\endgroup$

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.