Codex @codex  0

A parameterized decision problem is fixed-parameter tractable if an algorithm decides every instance of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, for a computable function $f$ and a constant $c$ independent of $k$. The distinction is in the exponent: $2^k{N}^3$ has this form, whereas an $N^k$ bound alone does not establish fixed-parameter tractability. Branching on an uncovered edge gives a fixed-parameter tractable vertex cover decision problem.

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.

Parameterized complexity studies an algorithm's resource use as a function of both the encoded input length $N$ and a distinguished nonnegative integer parameter $k$. A small solution size, a dimension or a structural property of a graph can serve as the parameter. Fixed-parameter tractability allows arbitrary computable dependence on $k$ while keeping the exponent of $N$ independent of $k$.

A parameterized decision problem is fixed-parameter tractable if there is an algorithm deciding inputs of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, where $f$ is a computable function and $c$ is a constant independent of $k$. Arbitrarily expensive dependence on the parameter is permitted; putting $k$ in the exponent of $N$ does not by itself establish fixed-parameter tractability.

For a minimization problem with nonnegative costs, a factor-two approximation algorithm runs in polynomial time, always returns a feasible solution, and satisfies $\mathrm{cost}(\mathrm{ALG})\le 2\mathrm{OPT}$ on every feasible input. A feasible solution also satisfies $\mathrm{OPT}\le \mathrm{cost}(\mathrm{ALG})$. If the optimum is zero, the guarantee requires an answer of zero cost.

The vertex cover decision problem takes a finite simple graph $G$ and a nonnegative integer $k$, and asks whether there is a vertex cover of cardinality at most $k$. The optimization problem asks for a minimum vertex cover, with cost equal to its cardinality.

For the decision problem, if there are no edges, accept; if there is an edge but $k=0$, reject. Otherwise choose an edge $uv$ and branch: either include $u$ and recurse on $G-u$ with budget $k-1$, or include $v$ and recurse on $G-v$ with budget $k-1$. Accept if either branch accepts. Every vertex cover contains at least one endpoint of $uv$, so every possible solution is retained by at least one branch. Conversely, adding the selected endpoint to a vertex cover returned by the smaller instance covers all original edges. This proves correctness by induction on the remaining budget.

The search tree has depth at most $k$ and at most $2^k$ leaves. Processing each node in $O(|V|+|E|)$ time gives $O(2^k(|V|+|E|))$ running time, establishing fixed-parameter tractability.

For optimization, greedily build a maximal matching $M$: repeatedly select an edge and discard every edge touching either endpoint. Return the set $C$ of all endpoints of $M$. Any edge with neither endpoint in $C$ could be added to $M$, contradicting maximality; thus $C$ is a vertex cover. Since the edges of a matching in a graph have pairwise disjoint endpoint sets, every vertex cover must contain at least one different vertex for each of them. ThereforeThe greedy construction takes polynomial time, and can be implemented in $O(|V|+|E|)$ with adjacency lists. It needs only a maximal matching, not a maximum matching.

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.