Cheat Sheets for Hard Problems

When we think about designing algorithms, we are usually very demanding in how we go about it: we require our algorithms to be fast and accurate on all conceivable inputs. This is asking for quite a bit, and perhaps it is not surprising that we cannot afford this luxury all the time. The good news is that most of the time we can make meaningful progress by relaxing just one of these demands. One approach that tackles all of these tradeoffs at once is to take what is now called a multivariate approach to the analysis of running times, which essentially involves appreciating that to describe a problem instance just in terms of its size is like describing a movie by a rating, which is unfortunate because there's so much more nuance. And yet we report — and think about — worst-case running times in only terms of the sizes of the instances. The parameterized approach takes into account problem structure by addressing secondary measurements (parameters), apart from the primary measurement of overall input size, that significantly affect problem computational complexity. The central notion of fixed parameter tractability (FPT) is a generalization of polynomial-time based on confining any non-polynomial complexity costs to a function only of these secondary measurements. In this talk, we will introduce this paradigm and illustrate its utility in theory and practice.