58 citations · 151 across the 35 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…
Hardness of discrepancy computation and epsilon-net verification in high dimension
Panos Giannopoulos, Christian Knauer, Magnus Wahlström +1
Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. There are two notions of discrepancy, namely continuous discrepancy and combina…
A Randomized Algorithm Based on Threshold Accepting to Approximate the Star Discrepancy
Michael Gnewuch, Magnus Wahlström, Carola Winzen
We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. An…