Parameterized algorithms 1000-2M12APW
The course is devoted to superpolynomial algorithms for NP-hard problems, especially to fixed-parameter algorithms. We plan to present the following topics:
1. Fixed-parameter algorithms: definition, motivation.
2. Branching algorithms. Measure & Conquer analysis.
3. Selected techniques in superpolynomial algorithms:
iterative compression, color coding, split&list, divide&conquer, important separators.
4. Applications of the inclusion-exclusion principle, the fast subset convolution algorithm.
5. Algebraic techniques (Schwarz-Zippel and Isolation Lemma).
6. Algorithms in graphs of bounded treewidth.
7. Subexponential algorithms in planar graphs: bidimensionality.
8. Lower bounds: W-hierarchy and Exponential Time Hypothesis.
Type of course
Course coordinators
Learning outcomes
Knowledge:
The student has advanced knowledge on designing and analyzing exact algorithms for NP-hard problems and discovering their limitations (K_W01, K_W02).
In particular, the student is able to start (on his own or in a team) research work in the aforementioned directions.
Skills:
* can design exact algorithm for medium-hard combinatorial NP-hard problem (K_U04)
* can (in a rigorous and formal way) analyse an algorithm, proving its correctness and discovering its complexity (K_U04)
* understands more specific complexity classes inside the NP class, with the most important case of the W-hierarchy; can place a given problem inside this hierarchy and conduct a simple hardness reduction (K_U05)
* can use literature and research articles (in English) (K_U14)
* can prepare short notes on a lecture (in English) (K_U13)
Competences
* understands the need to systematically read scientific articles to broaden and expand knowledge (K_K08)
* can formulate precise questions to deepen own understanding of the topic or to find the missing pieces of the reasoning (K_K02)
Assessment criteria
Quizzes after every lecture (via Moodle, 75% solved quizzes results in a +0.5 modifier to the grade from the oral exam), homeworks with problems (total number of points results in a modifier to the grade from the oral exam), and an oral exam (resulting in the final grade). Detailed rules available at moodle.
Bibliography
- Marek Cygan, Fedor Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015.
- Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010.
- Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford University Press, 2006.
- Jorg Flum, Martin Grohe, Parameterized Complexity Theory, Springer, 2006.
- Rod Downey, Mike Fellows, Parameterized Complexity, Springer, 1999.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: