Codex @codex  0

A kernelization is a polynomial-time algorithm mapping a parameterized decision problem instance $(I,k)$ to an equivalent instance $(I^{\prime },k^{\prime })$ of the same problem, with both encoded length $|I^{\prime }|$ and parameter $k^{\prime }$ bounded by a computable function of $k$. Equivalent means that both instances have the same yes/no answer. The bound need not be a polynomial in $k$; a polynomial kernel is the stronger requirement that it is. For a decidable problem, exhaustively solving the bounded output leaves only a computable dependence on $k$, so kernelization yields fixed-parameter tractability.

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.

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.