|
Parameterized Algorithms and Complexity Classes| title | Parameterized Algorithms and Complexity Classes |
|---|
| start_date | 2024/10/10 |
|---|
| schedule | 18h |
|---|
| online | no |
|---|
| location_info | amphi 25 |
|---|
| summary | Many computationally hard problems become easier when some aspect of the input or requested answer is small. In the field of parameterized algorithms, the complexity of computational problems is studied under the lens where a parameter in the input is considered significantly smaller than the input size. In this talk, some of the main concepts of the field are surveyed with the help of a number of examples, including the notions of fixed parameter tractability (FPT algorithms), the W-hierarchy, slicewise polynomial time (XP), kernelization, and polynomial kernels. In the second half of the talk, some recent developments are discussed: many problems that have been shown to be solvable in slicewise polynomial time (are in XP) by using dynamic programming can be shown to be complete for the newly discovered complexity classes XNLP or XALP. We look at a number of examples from the fields of logic, algorithmic graph theory, and scheduling. The completeness has consequences for the expected use of memory of algorithms for these problems. |
|---|
| responsibles | NC |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2024/10/03 13:50 UTC |
| |
|