114 citations · 306 across the 50 of their papers we have counts for
10 papers · 1 filter
Subexponential fixed-parameter tractability of cluster editing
Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk +2
In the Correlation Clustering, also known as Cluster Editing, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed in…
Clique cover and graph separation: New incompressibility results
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk +2
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. Although a framework for proving kerneliza…
Representative sets and irrelevant vertices: New tools for kernelization
Stefan Kratsch, Magnus Wahlström
The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch…
Hierarchies of Inefficient Kernelizability
Danny Hermelin, Stefan Kratsch, Karolina Sołtys +2
The framework of Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) allows us to exclude the existence of polynomial kernels for a range of problems under reasona…
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
Bart M. P. Jansen, Stefan Kratsch
The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite (i.e., 2-colorable) by deleting at most l vertices. We study structural parameterizations o…
Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem
Stefan Kratsch
Until recently, techniques for obtaining lower bounds for kernelization were one of the most sought after tools in the field of parameterized complexity. Now, after a strong influx…