Seminar with Professor Jan Arne Telle

16 september 2021, 4PM

Room 336 INESC-ID



“Coping with NP-hard problems by using parameterized algorithms”


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