Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 3 / c / ii

Write $U^{\prime }=U\setminus \{y\}$ and ${\mathcal{F}}^{\prime }=\{B\setminus \{y\}:B\in \mathcal{F}\}$. If $\mathcal{A}$ is a basis for the original instance, replace each member $A$ by $A\setminus \{y\}$. Deletion commutes with unions, so the resulting family generates every member of ${\mathcal{F}}^{\prime }$ and has at most $|\mathcal{A}|$ members.

Conversely, take a basis ${\mathcal{A}}^{\prime }$ for the reduced instance. Lift each of its members byIf $B\setminus \{y\}$ is represented as a union of reduced basis sets, the same union of their lifts agrees with $B$ on $U^{\prime }$. It contains $y$ exactly when one of the selected reduced basis sets contains $x$, namely exactly when $x\in B$. By the assumed incidence equivalence in a set family, this occurs exactly when $y\in B$. Thus the lifted union is precisely $B$, and the lifted basis has no more members.

Therefore deleting $y$ preserves the yes/no answer with the same parameter $k$. The reverse construction does not require a reduced basis set to be an input set.