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

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

Seminar with Professor Jan Arne Telle, Department of Informatics, University of Bergen

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

The event is finished.

About INESC-ID

INESC-ID, “Instituto de Engenharia de Sistemas e Computadores: Investigação e Desenvolvimento em Lisboa” is a Research and Development and Innovation Organization (R&D+i) in the fields of Computer Science and Electrical and Computer Engineering. INESC-ID mission is to produce added value to people and society, supporting the response of public policies to scientific, health, environmental, cultural, social, economic and political challenges. INESC-ID promotes cooperation between academia and industry by addressing research on daily life issues, such as healthcare, space, mobility, agri-food, industry 4.0, and smart grids. This high level of knowledge transfer is achieved through both competitive research projects and direct contracted research. Public and private entities have therefore access to a pool of knowledge, resources and services provided through the unique competencies available at the institution.

 

INESC-ID is supported by:

Join our newsletter

* indicates required

Subscriber consent

The data submitted through this form will be used exclusively for the sending of INESC-ID Newsletter, NEWS-ID, and will not, under any circumstances, be shared with third parties. If you choose to, you can easily unsubscribe from the newsletter by following the link presented in the footer. In that case, your data will be automatically deleted from our information system. If you need to update your contact information or clarify any questions related to the newsletter, please contact info@inesc-id.pt. By submitting this form, you give permission to the use of your personal data according to the conditions above.

We use Mailchimp as our marketing platform. By clicking below to subscribe, you acknowledge that your information will be transferred to Mailchimp for processing. Learn more about Mailchimp's privacy practices here.

});