PARAMTIGHT · Parameterized complexity and the search for tight complexity results

The joint goal of theoretical research in algorithms andcomputational complexity is to discover all the relevant algorithmic techniquesin a problem domain and prove the optimality of these techniques.We propose that the search for such tight results should be doneby a combined exploration of the dimensions running time, qualityof solution, and generality. Furthermore, the theory of parameterized complexityprovides a framework for this exploration.Parameterized complexity is a theory whose goal is toproduce efficient algorithms for hard combinatorial problems usinga multi-dimensional analysis of the running time. Instead ofexpressing the running time as a function of the input size only(as it is done in classical complexity theory), parameterizedcomplexity tries to find algorithms whose running time ispolynomial in the input size, but exponential in one or morewell-defined parameters of the input instance.The first objective of the project is to go beyond thestate of the art in the complexity and algorithmic aspects ofparameterized complexity in order to turn it into a theoryproducing tight optimality results. With such theory at hand, wecan start the exploration of other dimensions and obtain tightoptimality results in a larger context. Our is goal is being ableto prove in a wide range of settings that we understand all thealgorithmic ideas and their optimality.