Fixed Parameter Algorithms

Lecturer: Dr. Daniel Marx (Tel Aviv University).

About the lecturer | Course Summary

About the lecturer: Daniel Marx received a PhD from Budapest University of Technology and Economics in 2005. Then he was a research fellow in Hungarian Academy of Sciences and a postdoc in Budapest University of Technology and Economics. He is currently a postdoc in Tel Aviv University.
Daniel Marx is one of the leading researchers in the area of parameterized complexity. His other interests include constraint satisfaction problems, graph coloring, algorithmic graph theory, combinatorial optimization and computational complexity. He is an author of more than 40 research papers published in best journals and conferences. In recognition of his work, he was invited to serve as a program committee member of several conferences like ICALP, ESA, IWPEC and more.

Course summary:
Parameterized complexity is a relatively recent approach of dealing with hard computational problems. The main idea is that instead of expressing the running time as a function of the input size n, we analyze the running time as a multivariate function of the input size n and some parameter k of the input. Our goal is to develop algorithms that are efficient for small values of k, even if the input size n is large. The central notion of the area is fixed-parameter tractability (FPT): we say that a parameterized problem is FPT if it can be solved in time f(k)nc where f is an arbitrary (typically exponential) function of the parameter k and c is a constant. In other words, if a problem is FPT, then the combinatorial explosion can be restricted to the parameter k: for small fixed values of k, the problem can be efficiently solved, since the running time depends only polynomially on the input size.
It turns out that a wide range of interesting problems are FPT. Moreover, there is a very rich and interesting theory behind fixed-parameter tractability and a powerful toolkit of techniques have been developed in the past 15 years. The course will overview some of these algorithmic techniques (for example, kernelization, bounded search trees, color coding, iterative compression, treewidth, graph minors theory) and will give an introduction to the hardness theory of parameterized complexity.

Slides

Assignment
Tasks are here: [PDF]. Due: 15th Feb (please send pdf to Daniel Marx).