TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 16.11.2017

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Kernelization Lower Bounds for Finding Constant Size Subgraphs

Till Fluschnik (TU Berlin)

 

Kernelization is an important tool in parameterized algorithmics. The goal is to reduce the input instance of a parameterized problem in polynomial time to an equivalent instance of the same problem such that the size of the reduced instance only depends on the parameter and not on the size of the original instance. In this talk, we provide a first conceptual study on limits of kernelization for several polynomial-time solvable problems. For instance, we consider the problem of finding a triangle with negative sum of edge weights parameterized by the maximum degree of the input graph. We prove that a linear-time computable strict kernel of truly subcubic size for this problem violates the popular APSP-conjecture.

This is joint work with George B. Mertzios and André Nichterlein.

 

Date
Speaker
Location
Language
16.11.2017
16:15
Till Fluschnik
TEL 512
English

Back to the research colloquium site.

Nach oben

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe