02.11.14 - 07.11.14, Seminar 14451

Optimality and tight results in parameterized complexity

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Motivation

While many seemingly hard computational problems can be solved satisfactorily in practice, classical complexity dictates that they are in fact intractable (NP-hard) in general. This is an unsatisfactory situation since one would desire a more productive interplay between more heuristic practical results and theoretically proven theorems.

Parameterized complexity analyzes the complexity in finer detail by considering additional problem parameters beyond the input size and expresses the efficiency of the algorithms in terms of these parameters. In this framework, many NP-hard problems have been shown to be (fixed-parameter) tractable when certain structural parameters of the inputs are bounded. In the past two decades, there has been tremendous progress in understanding which problems are fixed-parameter tractable and which problems are not (under standard complexity assumptions).

In recent years, the field of parameterized complexity seems to have evolved beyond merely classifying problems as fixed-parameter tractable or not. The focus shifted to understanding how close the algorithmic results are to the ``best possible'' algorithm for the problem. Thanks to significant recent advances on both algorithms (upper bounds) and complexity (lower bounds), we have now a tight understanding of many problems and many algorithmic results can be now proven optimal under reasonable assumptions. Moreover, it turns out that the search for optimality can be formulated with respect to different aspects of parameterized complexity and each such aspect gives a separate challenging but doable research direction. One can consider the optimality of algorithms for parameterized problems (either fixed-parameter tractable or not), the optimality of preprocessing algorithms, and the optimality of algorithms with respect to the generality of the problem being solved. The goal of the seminar is to bring together experts in the area of parameterized complexity and algorithms, highlight these research directions and the relevant recent results, and discuss future research topics.