A polynomial Turing kernel to compute the cut-width of semi-complete digraph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2018

A polynomial Turing kernel to compute the cut-width of semi-complete digraph

Christophe Paul

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)
Fichier non déposé

Dates et versions

lirmm-02078882 , version 1 (25-03-2019)

Identifiants

  • HAL Id : lirmm-02078882 , version 1

Citer

Christophe Paul. A polynomial Turing kernel to compute the cut-width of semi-complete digraph. FILOFOCS 2018 - 7th French-Israeli Workshop on Foundations of Computer Science, Oct 2018, Paris, France. ⟨lirmm-02078882⟩
70 Consultations
0 Téléchargements

Partager

More