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.
Assignment
Tasks are here: [PDF].
Due: 15th Feb (please send pdf to Daniel Marx).