The Taub Faculty of Computer Science Events and Talks

There is a growing, vital need for fast algorithms for problems that are unlikely to admit efficient solutions, based on classical computational complexity theory. Parameterized Complexity is an exciting paradigm for coping with computationally hard problems, which is amazingly doable mathematically on a routine basis. In a nutshell, this paradigm aims to reduce the running times of algorithms for NP-hard problems, by confining the combinatorial explosion to a parameter k. In the past two decades, several techniques, known as ``color coding-related techniques'', led to the design of breakthrough parameterized algorithms. These techniques are non-standard in the extent in which they connect such seemingly disparate branches of Computer Science and Mathematics as matroid theory, linear algebra, graph theory and combinatorial optimization. In this talk, I present general schemes for mixing and improving upon color coding-related techniques. In particular, I discuss specific algorithms for classical problems such as k-Path, k-Internal Out-Branching and 3-Set k-Packing, as well as problems motivated by real-world applications to biological network queries, which are of major importance to systems biology.