Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

An efficient derandomisation for Color Coding

Color Coding is a method to design randomized FPT-algorithms for the embedding of structures of bounded treewidth and some related problems. The algorithms can be derandomised by the use of families of perfect hash functions. Considering as an example the parameterized path problem, p-Path, this talk presents the concept of Color Coding. I will show an algorithm for p-Path due to Alon, focusing on the choice of the hash functions and their representation by random variables of restricted independence. The talk will also include an outline of the construction of such random variables.