2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Relevant? en.wikipedia.org/wiki/Implicant $\endgroup$
    – D.W.
    Jul 27 '20 at 16:47
  • $\begingroup$ Interesting, I will try to read more about Karnaugh Maps when I can. Hopefully my context section makes sense? $\endgroup$ Jul 27 '20 at 18:02
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Jul 28 '20 at 9:15
0
$\begingroup$

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

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