Set basis problem ($\mathcal{F}\subseteq \{\bigcup \mathcal{B}:\mathcal{B}\subseteq \mathcal{A}\},|\mathcal{A}|\le k$)

The set basis problem asks whether a finite set family $\mathcal{F}\subseteq 2^U$ can be generated by unions of at most $k$ basis subsets of $U$. The basis sets need not belong to $\mathcal{F}$, and the empty union is allowed. For example, the three pairwise two-element subsets of $\{1,2,3\}$ have the singleton basis $\{\{1\},\{2\},\{3\}\}$, although none of its members is an input set.

There are at most $2^k$ distinct unions of $k$ basis sets, so any yes-instance has $|\mathcal{F}|\le 2^k$, after duplicate input sets are discarded. Retain one representative of each class of incidence equivalence in a set family. There are at most $2^{|\mathcal{F}|}\le 2^{2^k}$ representatives, because an element is described by its membership bits across $\mathcal{F}$. The equivalence-preserving deletion proof in incidence equivalence in a set family shows that this is a kernelization. Relabel the representatives and store the reduced incidence matrix; its length is bounded by a computable function of $k$. To solve the reduced instance with $q$ elements, enumerate all $2^{kq}$ ordered lists of $k$ basis subsets, padding smaller bases by empty sets. For each input set $B$, take the union of all proposed basis sets contained in $B$: it equals $B$ exactly when some allowable union represents $B$. This finite search proves fixed-parameter tractability.