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

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.