Parameterized algorithms

elective monographs

The course is devoted to superpolynomial algorithms for NP-hard problems, especially to fixed-parameter algorithms. The target audience are masters and PhD students interested in algorithmics and combinatorics, considering future scientific career (including only at the level of masters thesis).

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.

- 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.

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)

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.