Color-coding and derandomization
I’d like to re-emphasize the power of randomization in the $k$-PATH algorithms we saw in class. Recall that it accomplished two properties:
(1) The randomized process succeeded with probability $1/f(k)$ for some $f$ (no dependence on $n$). We could then repeat the algorithm, say, $100f(k)\log(n)$ times.
(2) It established a special structure in the target solution (a $k$-path, in this case), without knowing the target solution! This enabled us to find this target solution in FPT time by exploiting its special structure.
I think the “without knowing the target solution” is really what made it work. There are potentially $n^k$ many paths, but a successful iteration of color-coding allowed us to extract information from the target $k$-path, without ever locating it in the space of $n^k$ potential target solutions.
Of course, a natural follow-up question is: can we make this procedure deterministic? In other words, can we derandomize it?
Let’s first explain what we mean by derandomization. First, let’s view each labeling as a vector of size $n$, with coordinate entries in $[k]$. (That is, each vector lies in $[k]^n$.) To derandomize color-coding, we want to select a set of $f(k)\text{poly}(n)$ many vectors (labelings) beforehand, deterministically, and then run the algorithm on each labeling. As long as the special structure of the target solution is established in one of the vectors, we’re all set. Such a family of vectors exists, and is called a perfect hash family:
Definition (Perfect hash family): A family $\mathcal F$ of vectors in $[k]^n$ is a perfect hash family if for every subset $S\subseteq [n]$ of size $k$, there exists a vector in $\mathcal F$ that has a different entry at each coordinate in $S$. In other words, its restriction to the coordinates in $S$ is some permutation of $[k]$.
Not only do perfect hash families give us what we want (for $k$-path), they say something stronger: Given $n$ and $k$, we can find $f(k)\text{poly}(n)$ many vectors such that for all instances $(G,k)$ where $G$ has $n$ vertices, the algorithm will find the $k$-path. That is, we can use the same hash family for all instances $(G,k)$ of size $n$!
What’s the size of this perfect hash family? The size can be made $O(e^{k+O(\log^2k)} \log n)$; it’s only slightly worse than choosing $O(e^k\log n)$ vectors at random, since $\log^2 k \ll k$.
Kernelization
I didn’t have time to define kernelization formally, so here it is. Let’s assume we’re in the decision version of a problem, that is, the answer is either YES or NO. (For example, from class: does the graph have a vertex cover of size $k$?)
Definition (Kernelization): A kernelization algorithm inputs $(G,k)$, runs in polynomial time, and outputs $(G’,k’)$ such that:
(1) $(G,k)$ is YES instance $\iff$ $(G’,k’)$ is YES instance
(2) $\vert G’\vert \le f(k’)$ for some function $f:\mathbb N\to\mathbb N$. Of course, the “size” of $G’$ is not well-defined, but if $G$ is a graph, you can usually think of it as number of vertices or number of edges.
(3) $k’ \le k$. This is important, since the whole purpose is to solve the smaller instance $(G’,k’)$ in FPT time (in $k’$).
It turns out that kernelization is the most interesting when the function $f$ from (2) is polynomial. That is, $\vert G\vert \le \text{poly}(k)$. In this case, we call it a polynomial kernelization algorithm, or polynomial kernel for short.
Recall that the kernelization algorithm for Vertex Cover satisfied $\vert V\vert \le k^2+k$, so it’s a polynomial kernel.
Obviously, if an algorithm has a polynomial kernel (or any kernel), it’s FPT, because we can pay $\text{poly}(n)$ time to reduce to the kernel, and then brute force on the $f(k)$-sized kernel. It turns out that the reverse is not true: not all FPT problems have polynomial kernels. For example, while the $k$-PATH problem is FPT as shown in lecture, it’s been proven that it doesn’t have any polynomial kernel! There’s even a subfield dedicated to showing such kernelization lower bounds.
However, if you remove the “polynomial” away from kernel, then the reverse is true: all FPT problems have a kernel for some (possibly exponential or worse) $f$. The proof for this is not very instructive, but the point is that restricting ourselves to polynomial kernels says something meaningful.