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.
Course coordinators
Type of course
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.