Questa pagina descrive il corso di dottorato “Algorithmic Techniques Beyond Polynomial Time: Parameterization and Subexponentiality“, tenuto dal Prof. Link identifier #identifier__180562-1Giordano Da Lozzo
Date
-
09/11 h 15:00 – 17:00 – sala riunioni (grande o piccola)
-
10/11 h 14:00 – 16:00 – sala riunioni (grande o piccola)
-
11/11 h 15:00 – 18:00 – sala riunioni (grande o piccola)
-
13/11 h 15:00 – 18:00 – sala riunioni (grande o piccola)
Abstract:
Many computationally challenging problems admit efficient solutions once we look beyond the classical notion of polynomial-time tractability. This PhD course provides an introduction to two complementary approaches for designing algorithms for hard combinatorial problems: parameterized algorithms and subexponential algorithms.
The first part focuses on subexponential algorithms, exploring techniques that lead to running times significantly below the generic 2^{O(n)} bound. We will discuss structural decompositions, separators, treewidth-based methods, and other techniques for obtaining 2^{o(n)} or 2^{O(\sqrt{n})}-time algorithms.
The second part introduces fixed-parameter tractability (FPT), where the complexity of a problem is studied with respect to a parameter k. We will cover fundamental techniques such as bounded search trees, kernelization, parameterized dynamic programming, and iterative compression, together with the basic concepts of parameterized complexity.
The course emphasizes the algorithmic ideas behind these techniques and their application to hard problems in graph algorithms and combinatorial optimization.
25 Agosto 2026