Résumé
The existence of a fixed-parameterized algorithm is equivalent to the existence of a kernelization algorithm, that is a polynomial time that given a parameterized instance compute an equivalent instance, so-called kernel, the size of which is bounded by the parameter. However, recent lower bound techniques allows to establish, under some standard complexity hypothesis, the non-existence of a polynomial size kernel. This raised the question of designing polynomial time algorithms that instead of reducing the input instance to one kernel, computes polynomially many kernel from which the original instance can be solved. This is known under the concept of Turing-kernlization. In this talk, we provide such an algorithm for the parameterized cut-width problem in semi-complete digraphs. To date, this provides one of the very few examples of non-trivial Turing kernelization.This work was done with Florian Barbero (Montpellier University) and Michal Pilipczuk (Warsaw University)