A dominating set in a graph is a subset $D$ of the vertices such that every vertex in the graph either belongs to $D$ or is adjacent to $D$. Use backtracking to show that, in graphs with maximum degree three, a dominating set of $k$ vertices (if one exists) can be found in fixed-parameter-tractable time.
A complete bipartite cover of a graph $G$ is a collection of complete bipartite subgraphs of $G$ that together include every edge in $G$. The size of a complete bipartite cover is the number of complete bipartite subgraphs in it. Use kernelization to show that finding a complete bipartite cover of size $k$ (if one exists) is fixed-parameter tractable.
An algorithm is defined to be fixed-parameter tractable if its running time is $O(f(k)p(n))$ where $n$ is the input size, $k$ is the additional parameter we're using to analyze the algorithm, $p$ is a polynomial that does not depend on $k$, and $f$ is an arbitrary (computable) function. Define an algorithm to be strongly fixed-parameter tractable if its running time is instead $O(f(k)+p(n))$ for a (possibly different) computable function $f$ and polynomial $p$. Show that every fixed-parameter tractable algorithm is strongly fixed-parameter tractable.
In class we analyzed the time for finding $k$-vertex paths, using color-coding with $k$ colors, as $$O(\frac{k^k}{k!}2^k(n+m)).$$ Suppose we use $k+1$ colors instead of $k$ colors. Would the time be slower or faster, and by how much?