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?