Example. \(k\)-Vertex cover: is there a set of \(k\) vertices “covering” all the edges? (i.e., so that there is a vertex incident to every edge).

1. Kill isolated vertices
2. Always take vertices of degree larger than \(k\)
3. In a max-degree \(d\) graph you can’t hope to cover more than \(kd\) edges. So we can instantly identify as no-instances graphs with too many edges.

By applying these rules we can in \(n^{O(1)}\) time reduce \(k\)-vertex cover to an instance of size \(O(k^{2})\) edges and \(O(k^{2})\) vertices.

Then you can brute force solve the kernel in time \(\binom{k^{2}}{k}\).

Remark: this is by no means the best kernel for vertex cover.

Example. \(k\)-vertex cover is a good example here too. You can either take a vertex or take all of its neighbors.

The algorithm is then:

• “base case”: if the max degree ever drops to \(2\) then apply a trivial algorithm to determine the vertex cover
• otherwise, branch on the highest degree vertex (i.e., chose it or chose its neighbors).

The nice part: this search tree can have depth at most \(k\). In fact, you can even say some stronger stuff like the number of leaves of the tree will be at most \(\phi^{k}\) where \(\phi^{k}\) is the \(k\)-th fibonacci number, because you can write a nice reccurrence. I think you maybe even get a better exponential thing.

Example. Longest Path. I.e., is there a path (no repeated vertices) of length \(k\)?

Randomly color vertices with \(k\) colors. Probability that your path is rainbow is like \(e^{-k}\).

We can find rainbow paths with DP.

Example. isomorphic subgraph given \(H,G\) where \(H\) is a \(k\)-vertex graph and \(G\) is a max-degree \(d\) graph determine whether \(H\) is isomorphic to any subgraph of \(G\).

For simplicity imagine that \(H\) is connected.

randomly 2-color edges of \(G\). hope that this results in a copy of \(H\) in \(G\) being highlighted by the colors.

Search over connected components in the colorful subgraph for one isomorphic to \(H\).