| Title | : | CSE Bytes: Measuring Toughness of Graphs, FPT-Approximation Style |
| Speaker | : | Akanksha Agrawal (IITM) |
| Details | : | Fri, 3 Feb, 2023 2:30 PM @ CS15 |
| Abstract: | : | Several frameworks have been designed to cope with NP-hardness, and two such vibrant frameworks are Parameterized Algorithms and Approximation Algorithms. Each of these frameworks come with their own limitations, and in this talk we will talk about the recent trend of combining these two worlds for problems related to some structural measure of hardness of graphs. The framework of Parameterized Algorithms can be thought of as a multivariate analogue of the Classical Complexity Theory. Here, in addition to the input size, we aim to study how an inherent toughness of the input/output (or some combination of them) affects the runtime complexity of the problem. One of the central goals in Parameterized Algorithms is to design an algorithm, called an FPT algorithm, for the given problem with running time f(k).n^{O(1)}, where n is the input size and k is a measure of a toughness of the input/output (or some combination of them). The above running time is called an FPT time. One of the central goals in the field of Approximation Algorithms is to compute a solution that is provably not very far from an optimal solution. For certain problems even reasonable approximation algorithms do not exist under the very well-believed conjectures. This has led to the development of the framework of FPT-approximations, where the objective is to compute a solution that is provably not very far from an optimal solution, in FPT time. In this talk we will focus on computing graph width measures, that give us a measure of "toughness" of graphs, under the lens of FPT-approximation. Our particular focus will be on a measure called tree-depth. |
