Efficient Implementation of Boolean Lattice-Esque Operation

Question

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'$.

Answer 1

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$.