An introduction to the parameterized complexity

• Grant number: 21/07076-9
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: November 01, 2021
• End date: October 31, 2022
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Carla Negri Lintzmayer
• Grantee: Gustavo da Silva Teixeira
• Host 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)