= Solution
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 column
$$
\sigma(x)=\bigl(\mathbf1_{x\in B}\bigr)_{B\in\mathcal F}\in\{0,1\}^m.
$$
Keep one element from each class of equal columns. By repeatedly applying part (ii), this preserves the answer. The reduced number of elements $q$ satisfies
$$
\boxed{m\leq2^k,\qquad q\leq2^m\leq2^{2^k}.}
$$
Relabel 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 \b[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.
Back to article page
