114 citations · 306 across the 50 of their papers we have counts for
8 papers · 2 filters
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…
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…
Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal
Stefan Kratsch, Magnus Wahlström
The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite by deleting at most of its vertices. In a breakthrough result Reed, Smith, and Vetta (O…
Kernel Bounds for Path and Cycle Problems
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch
Connectivity problems like k-Path and k-Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recen…