Profile
Profile

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
Date of birth: 12.Mar 1983
Mathscinet-Number: 939434

Academic Career

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

Publication List

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
Download Profile