# Efficient Implementation of Boolean Lattice-Esque Operation

Let $$X = \{1,2,\dots n\}$$, and $$Y_i= \{T \in \mathcal{P}(X): |T| \le i\}$$. I am interested in "avoidance sets" $$A \subset Y_n$$. We say a subset $$S \subset X$$ is valid with respect to an avoidance set $$A$$ if $$T \not \subseteq S$$ for all $$T \in A$$.

We let $$f(A)$$ denote the set of $$S\subset X$$ that are valid with $$A$$. It may be helpful to note that $$f(A' \cup A'') = f(A')\cap f(A'')$$.

Given a list of avoidance sets $$A_1,A_2,\dots A_k \in Y_2$$, I want to return an avoidance set $$A' \in Y_2$$ such $$\bigcup_{1 \le i \le k} f(A_i) \subseteq f(A')\tag{1}$$ and for any other $$A'' \in Y_2$$ satisfying (1), we do not have $$f(A'') \subsetneq f(A')$$.

Can this be done in time linear to $$\sum_{1\le i \le k} |A_i|$$? (you may assume that all the sets $$A_i$$ are simplified, i.e. if $$\{a\}\in A_i$$ and $$\{b\}\in A_i$$ then $$\{a,b\} \not \in A_i$$)

Context:

The physical motivation behind my question is that I am trying to "roughly" keep track of events which must be avoided.

An element $$x \in X$$ corresponds to an "event" occurring in a probability space. A subset $$S \subset X$$ correspond to the intersection all the events $$x_1,x_2 \dots x_k \in S$$ occurring at once.

An avoidance set $$A$$ is supposed to express certain events which have probability zero of occurring. (so $$S \subset X$$ is not valid with $$A$$ if the event corresponding to $$S$$ has zero probability) To keep the cost of space low, I have decided to concern myself with only working with avoidance sets in $$Y_2$$. (thus this is a heuristic representation)

Now, let's say I am keeping track of avoidance sets $$A_i$$ where $$S$$ is invalid with $$A_i$$ represents that $$S$$ has probability zero given event $$i$$ happens. Now, if I know at least one of the events $$A_1,\dots A_k$$ occurs, then I am interested in finding $$A'$$.

• Relevant? en.wikipedia.org/wiki/Implicant
– D.W.
Jul 27, 2020 at 16:47
• Interesting, I will try to read more about Karnaugh Maps when I can. Hopefully my context section makes sense? Jul 27, 2020 at 18:02
• I think the desired $A'$ is given by $A' = \{T : \forall T' . T \subseteq T' \implies T' \notin \cup_i f(A_i)\}$. I don't know if this helps, as it doesn't describe how to compute $A'$ in linear time. In the special case where $k=2$, I think this becomes $A' = \{T_1 \in A_1 : \exists T_2 \in A_2 . T_2 \subseteq T_1\} \cup \{T_2 \in A_2 : \exists T_1 \in A_1 . T_1 \subseteq T_2\}$, which should be computable in linear time if you're working in $Y_2$. I imagine this could probably be extended to arbitrary $k$, by doing two at a time. Does that look right to you?
– D.W.
Jul 28, 2020 at 9:15

I believe the desired $$A'$$ is given by

$$A' = \{T : \forall T' . T \subseteq T' \implies T' \notin \cup_i f(A_i)\}.$$

Here is how to compute $$A'$$ in linear time from the $$A_i$$'s. Basically, we want to include the set $$T$$ if: (1) for all $$i$$, there exists $$T_i \in A_i$$ such that $$T_i \subseteq T$$ and (2) there exists $$j$$ such that $$T \in A_j$$. You can find those sets as follows:

• For each $$T \in A_1 \cup \cdots \cup A_k$$:
• Set flag := true.
• For each $$i := 1,2, \dots, k$$:
• If $$\not\exists T_i \in A_i$$ such that $$T_i \subseteq T$$, set flag := false.
• If flag := true, output $$T$$.

Naively, this seems likely to take quadratic time or more. However, since you're working in $$Y_2$$, there is a more efficient algorithm. For each $$i$$, build a hashtable (an index) that, given $$T$$, lets you check whether $$T \in A_i$$. Then, you can implement the algorithm above as:

• For each $$T \in A_1 \cup \cdots \cup A_k$$:
• Set flag := true.
• For each $$i := 1,2, \dots, k$$:
• If $$|T|=2$$: suppose $$T=\{u,v\}$$; if $$T \notin A_i$$ and $$\{u\} \notin A_i$$ and $$\{v\} \notin A_i$$, then set flag := false.
• Otherwise if $$|T|=1$$: if $$T \notin A_i$$, then set flag := false.
• If flag := true, output $$T$$.

This can now be implemented in time proportional to $$k \sum_i |A_i|$$. I don't know whether this is efficient enough for you.

I think for this to work corretly in all cases, you might need to first convert each avoidance set $$A_i$$ into canonical form. The canonical form of avoidance set $$A$$ is an avoidance set $$A^*$$ with the smallest number of sets such that $$f(A^*)=f(A)$$. When working in $$Y_2$$ you can compute the canonical form with the following rules:

• Rule 1: If $$\{u,v\} \in A$$ and $$\{u\} \in A$$ or $$\{v\} \in A$$, delete $$\{u,v\}$$ from $$A$$.

• Rule 2: If $$\{x,u\} \in A$$ for each $$x \in \{1,\dots,n\}\setminus\{u\}$$, then add $$\{x\}$$ to $$A$$ and remove all $$\{x,u\}$$ from $$A$$.

You can enforce Rule 1 with a linear scan over $$A$$; and then you can enforce Rule 2 with a simple linear-time graph algorithm (build the undirected graph with an edge for each $$\{u,v\} \in A$$; check the degree of each vertex; apply Rule 2 to each vertex with degree $$n-1$$). So, at least when working in $$Y_2$$, you can convert an avoidance set to canonical form in linear time. I haven't tried to think about a generalization to arbitrary $$Y_i$$.