Advanced search
Start date
Betweenand

An introduction to the parameterized complexity

Grant number: 21/07076-9
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): November 01, 2021
Effective date (End): October 31, 2022
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Carla Negri Lintzmayer
Grantee:Gustavo da Silva Teixeira
Home Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil

Abstract

When dealing with computational problems, we always try to find efficient algorithms that solve them, for all possible instances. The concept of efficiency of an algorithm usually refers to its time complexity being polynomial on the input size. However, there are many relevant problems for which there is no hope that we will find efficient algorithms that find optimal solutions for all instances. These problems constitute the NP-hard and NP-complete classes. Such problems, often having important applications in the real world, still need some solution and, among the alternatives to deal with them, we could think of algorithms that, even not being efficient, would return optimal solutions with less time consumption. Parameterized complexity theory proposes an alternative toward this, studying algorithms that find optimal solutions for all instances of these problems in exponential time, but whose exponential complexity does not depend on the entire input size, but on a value called parameter, which represents the size of a particular aspect of the input, usually much smaller than the input itself. Problems that admit such algorithms are called fixed-parameter tractable (FPT), and constitute the class of problems also called FPT. This scientific initiation project aims to introduce the candidate to the parameterized complexity theory, providing an overview of the area, studying the main problems involved, the main techniques for developing algorithms to deal with FPT problems, and some of the most important results obtained in the area so far.(AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Please report errors in scientific publications list by writing to: cdi@fapesp.br.