Parameterized Complexity as a New Computational Lens

29/12/2016 - 12:00

Parameterized Complexity was introduced in the 1990s by Downey and Fellows. Nowadays, various aspects of this field are ubiquitous, vibrant areas of research. In a nutshell, Parameterized Complexity aims to reduce the running times of algorithms for NP-hard problems by confining the combinatorial explosion to a parameter k. More precisely, a problem is fixed-parameter tractable (FPT) with respect to a parameter k if it can be solved by an algorithm, called a parameterized algorithm, whose time complexity is bounded by f(k)n^{O(1)} for some function f that depends only on k. By careful examination of real datasets, one can choose a parameter k that will often be significantly smaller than the input size n. Indeed, parameterized problems arise in a variety of areas outside of pure theoretical computer science and math.


In this talk, I give a brief overview of some of my recent contributions in Parameterized Complexity. In the first part of my talk, I present results in core research areas such as Kernelization and Parameterized Algorithms. Here, problems are primarily concerned with graphs. However, in practice, inputs are not necessarily graphs. In the second part of my talk, I address this issue. Here, I describe my foray into input domains that consist of polygons, preferences and matrices.