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