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