Advanced Topics 2 (236 602):
Parametrized Complexity
Homepage:
http://cs.technion.ac.il/~janos/COURSES/FPT/announcement.html
Lecturer: Prof. J.A. Makowsky
Taub 628, Tel: 4358, e-mail: janos@cs
Format: 2 hours lecture
Lecture: Sunday 14:30-16:30
Place: To be announced
Prerequisites:
Computability (236 343), Graph Algorithms (234 246)
Course outline:
The course deals witrha methods of classifying and solving
problems which are at least NP-hard.
The good problems are the Fixed Parameter Tractable Problems (FPT),
which are those which can divided into subproblems
P(k), which are solvable in polynomial time f(k) n^c with
the constant c not dependent on k.
There is also a hierarchy of bad parametrized problems,
for which it can be shown,
that no such algorithms exist unless this hierarchy collapses.
We shall develop the theory of parametrized complexity.
We shall present a wealth of parametrized problems
which are FPT, which includes many variations of SAT,
graph problems, and classical optimization problems such as TSP.
Course goal
Leading to the frontier of current research
in parametrized complexity.
Introducing topics for
M.Sc. and Ph.D. theses.
Course requirements
Projects or take home exam.
Literature
-
R.G. Downey and M.F Fellows,
Parametrized Complexity, Springer, 1999.
-
Additional literature from Journals.