Homepage

Stefan Kratsch

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E 1 4, Room 328
66123 Saarbrücken
Germany

Email: Get my email address via email
Phone: +49 681 9325 128
Fax: +49 681 9325 199

Research Interests

Parameterized complexity, especially kernelization
Complexity classes
Approximation algorithms
Graph problems, constraint satisfaction problems

Publications

Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch. Kernel Bounds for Path and Cycle Problems. In IPEC 2011.
Jiong Guo and Iyad Kanj and Stefan Kratsch. Safe approximation and its relation to kernelization. In IPEC 2011.
Bart M. P. Jansen and Stefan Kratsch. On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal. In IPEC 2011.
Bart M. P. Jansen and Stefan Kratsch. Data Reduction for Graph Coloring Problems. In FCT 2011.
Pinar Heggernes and Pim Van 'T Hof and Bart Jansen and Stefan Kratsch and Yngve Villanger. Parameterized Complexity of Vertex Deletion into Perfect Graph Classes. FCT 2011.
Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. ICALP 2011.
Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch. Cross-Composition: A New Technique for Kernelization Lower Bounds. STACS 2011.
Danny Hermelin and Chien-Chung Huang and Stefan Kratsch and Magnus Wahlström. Parameterized Two-Player Nash Equilibrium. WG 2011.
S. Kratsch and D. Marx and W. Wahlström. Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. In MFCS 2010.
S. Kratsch and M. Wahlström. Preprocessing of Min Ones Problems: A Dichotomy. In ICALP 2010
S. Kratsch and P. K. Lehre and F. Neumann and P. S. Oliveto. Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutation. In PPSN 2010.
S. Kratsch and P. Schweitzer. Isomorphism of Graphs of Bounded Feedback Vertex Set Number. In SWAT 2010.
K. Jansen and S. Kratsch and D. Marx and I. Schlotter. Bin Packing with Fixed Number of Bins Revisited. In SWAT 2010.
S. Kratsch and M. Wahlström. Two Edge Modification Problems Without Polynomial Kernels. In IWPEC 2009.
S. Kratsch and F. Neumann. Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem. In GECCO 2009. (Best Paper Award).
S. Kratsch. Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP. In STACS 2009.

Academic Appointments

September 2011 - present:
PostDoc at Utrecht University supported by NWO project "KERNELS"

Education

March 2008 - August 2010:
Ph. D. student in Computer Science at the Universität des Saarlandes, Saarbrücken, Germany and the Max-Planck-Institute for Informatics
Title of Ph.D. thesis: Kernels for generic problems: Upper and lower bounds (supervisor: Prof. Dr. Kurt Mehlhorn)
October 2002 - February 2008:
Studies in Computer Science at the Friedrich-Schiller University in Jena
Title of Master's Thesis (Diplomarbeit): Problem kernels for NP-hard edge modification problems: Chain Deletion and Chordal Completion (supervisor: Prof. Dr. Rolf Niedermeier)