Dear All,
We will have the following seminar by Professor Jan Arne Telle, Department of
Informatics, University of Bergen, on September 16th.
Title: Coping with NP-hard problems by using parameterized algorithms
Date: 2021-Sep-16 Time: 16:00
Room: INESC-ID 336
Abstrat: The talk will give an introduction to the field of parameterized
complexity, which focuses on classifying computational problems according to
their inherent difficulty with respect to /multiple/ parameters of the input.
The complexity of a problem is then measured as a function of those
parameters.
This allows the classification of NP-hard problems on a finer scale than in
the classical setting, where the complexity of a problem is only measured as a
function of the number of bits in the input.
We will give some concrete applications:
1. A kernelization algorithm for k-Vertex Cover (k-VC, use natural parameter).
2. A Fixed Parameter Tractable (FPT) algorithm for k-VC.
3. Dominating Set (DS) is not FPT for the natural parameter.
4. Introduce Treewidth tw.
5. DS is FPT parameterized by tw.
6. A hierarchy of graph parameters.
7. An application to satisfiability.
Best regards,
Alexandre Francisco