Set basis problem
= Set basis problem
{title2=$\mathcal F\subseteq\{\bigcup\mathcal B:\mathcal B\subseteq\mathcal A\},\quad|\mathcal A|\leq k$}
= SetBasis
{c}
{synonym}
The <set basis problem> asks whether a finite <set family> $\mathcal F\subseteq2^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|\leq2^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|}\leq2^{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>.