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

If the basis has $r\le k$ members, it has $2^r$ subsets, each specifying a possible union. Different subsets can produce the same union, so the number of distinct generated sets is at most $2^r$. Consequently,Here $\mathcal{F}$ is a set family of distinct sets. If a representation lists duplicate input sets, discard those duplicates before applying this bound. The empty union is included.

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.

First discard duplicate input sets, and let $m=|\mathcal{F}|$. If $m>2^k$, reject by part (i); this rejection can be encoded as the fixed no-instance $U=\{u\}$, $\mathcal{F}=\{\{u\}\}$, $k=0$ of the set basis problem. Otherwise, represent each ground element $x$ by its incidence columnKeep one element from each class of equal columns. By repeatedly applying part (ii), this preserves the answer. The reduced number of elements $q$ satisfiesRelabel these representatives and store their reduced incidence matrix. Its $mq$ membership bits, the dimensions and $k$ have encoded length bounded solely by a computable function of $k$; the leading incidence bound is $2^{k+2^k}$. Thus this is a kernelization, even though it is not a polynomial kernel. Forming columns and grouping identical ones takes polynomial time in the original explicit input length. To test $m>2^k$, compare bit lengths or truncate exponentiation at $m+1$; never construct an enormous $2^k$ merely to perform this preprocessing comparison.

For completeness, the bounded instance can be solved explicitly. Enumerate all ordered lists of $k$ subsets of the $q$-element ground set, allowing empty members to pad shorter bases. There are at most $2^{kq}$ such lists. For a candidate basis and each reduced input set $B$, form the union of every candidate basis set contained in $B$. If this union equals $B$, a representation exists; if it does not, no union of that candidate's members can represent $B$, because any member not contained in $B$ would add a forbidden element. Testing every $B$ therefore verifies a candidate in time polynomial in $m,q,k$.

The preprocessing is polynomial in the original input length, and the remaining search depends only on $k$. Hence the set basis problem is fixed-parameter tractable with respect to $k$. Empty input families and $k=0$ are covered by the same empty-union convention.