I am looking for the name (and, possibly, an efficient solution) of the following problem:
Given a Boolean lattice $(L, \sqcap, \sqcup)$ with least element $0$, and a finite subset $X \subseteq L$, find a minimal set $Y \subseteq L$ such that
- $\forall y_1, y_2 \in Y: y_1 \sqcap y_2 = 0$
- $\forall x \in X: \exists Y' \subseteq Y: \bigsqcup Y' = x$
- $\bigsqcup X = \bigsqcup Y$
If L is a subset lattice, then this problem is a version of the "set basis problem" with an additional disjointness requirement. However, it should be generalizable to Boolean lattices.
An efficient algorithm to calculate a disjoint set basis is to enumerate all elements in $\bigcup X$, and compute the equivalence relation of elements which occur in exactly the same set of elements in $X$. However, this algorithm is only efficient because the representation of sets is not succinct. If we, on the other hand, consider BDDs as a model for Boolean formulae, each element of $X$ may represent exponentially many "atoms" (formulae with a unique satisfying assignment) of $L$.
The following (naive) algorithm should suffice to solve the problem in the general setting:
- Let $X = \{x_1, \ldots, x_n\}$
- Initialize $Y := \emptyset$
- For $k = n, \ldots, 1$:
- For each $X' \subseteq X$ such that $|X'| = k$:
- Let $y := \sqcap X'$
- If $y \neq 0$:
- $Y := Y \cup \{y\}$
- For all $i = 1, \ldots, n$:
- $x_i := x_i \sqcap y^\complement$
- For each $X' \subseteq X$ such that $|X'| = k$:
However, clearly enumerating over all subsets of $X$ is inefficient. It is not hard to come up with some engineering tweaks, but what I am rather looking for is a name for this problem to start researching about it.
Many thanks!