# Prof. Dr. Stefan Kratsch

E-mail: kratsch(at)cs.uni-bonn.de
Phone: +49 228 73 4554
Fax: +49 228 73 4321
Homepage: http://www.i1.informatik.uni-bonn.de/doku.php?id=en:staff:stefankratsch
Institute: Institute of Computer Science
Research Area: Research Area KL

 2010 Dr. rer. nat., Max Planck Institute for Informatics, Saarland 2010 - 2012 Postdoc, Utrecht University, Netherlands 2012 - 2012 Postdoc, Max Planck Institute for Informatics, Saarland 2012 - 2014 Junior Research Group Leader, TU Berlin Since 2015 Professor (W2), University of Bonn

## Research Profile

Most of my research so far is within the field of parameterized complexity. Mainly, the field studies NP-hard problems and seeks to understand the influence of problem parameters on the problem complexity; in particular, one seeks algorithms that are fast when certain parameters are small. As an example, many optimization problems are expected (under the so-called exponential-time hypothesis) to take time $O(a^n)$ to exactly solve (worst-case) inputs of size $n$ for some $a > 1$. However, if the task is only to find a solution of size at most $k$ (or find that none exists) then this can often be done in time, e.g., $O(b^k n^c)$, that is, with only polynomial dependence on the input size. The same can of course be asked when $k$ instead stands for some structural parameter as for example the treewidth of input graphs. The field also has various techniques for getting lower bounds on running times or ruling out time $O(f(k) n^c)$ for all functions $f$ (modulo complexity assumptions). From such considerations we get two things: First, we may find algorithms that are sufficiently fast at solving our problem for a range of the parameter that actually occurs in practice. Second, we get a better understanding of what makes a problem hard and we may be able to deduce a different, hopefully more tractable, problem formulation. Multivariate analysis of computational problems is a very general perspective (predating parameterized complexity) and can also be used to talk about approximation schemes, adaptive algorithms, or data structures.

## Research Projects and Activities

DFG Emmy Noether-Project „Efficient preprocessing of hard problems“
since 2012

Steering Committee of the International Symposium on Parameterized and Exact Computation (IPEC)
Member, 2015 - 2018, chair of the committee, since 2016

## Selected Publications

[1] Eva-Maria C. Hols, Stefan Kratsch
A Randomized Polynomial Kernel for Subset Feedback Vertex Set
33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France
of LIPIcs : 43:1--43:14
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
2016
ISBN: 978-3-95977-001-9
DOI: 10.4230/LIPIcs.STACS.2016.43
[2] Stefan Kratsch, Geevarghese Philip, Saurabh Ray
Point line cover: the easy kernel is essentially tight
ACM Trans. Algorithms , 12: (3): Art. 40, 16
2016
DOI: 10.1145/2832912
[3] Stefan Kratsch
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
ACM Trans. Algorithms , 10: (4): Art. 19, 16
2014
DOI: 10.1145/2635808
[4] Marek Cygan, Stefan Kratsch, Jesper Nederlof
Fast Hamiltonicity checking via bases of perfect matchings
STOC'13---Proceedings of the 2013 ACM Symposium on Theory of Computing
Publisher: ACM, New York
2013
DOI: 10.1145/2488608.2488646
[5] Stefan Kratsch, Magnus Wahlström
Representative sets and irrelevant vertices: new tools for kernelization
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science---FOCS 2012
Publisher: IEEE Computer Soc., Los Alamitos, CA
2012

## Awards

 2009 Best Paper Award of the Genetic and Evolutionary Computation Conference 2012 DFG Emmy Noether-Grant 2016 Best Paper Award of the 24th Annual European Symposium on Algorithms 2016 Teaching Award of the University of Bonn

## Supervised Theses

• PhD theses: 3, currently 3