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 Access content directly
Conference Papers Year : 2018

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

Christophe Paul

Abstract

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)
No file

Dates and versions

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

Identifiers

  • HAL Id : lirmm-02078882 , version 1

Cite

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⟩
62 View
0 Download

Share

Gmail Mastodon Facebook X LinkedIn More