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

Publications in refereed journals:

Stefan Kratsch and Frank Neumann. Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem. To appear in Algorithmica, Springer.
Danny Hermelin and Chien-Chung Huang and Stefan Kratsch and Magnus Wahlström. Parameterized Two-Player Nash Equilibrium. To appear in Algorithmica, Springer.
Klaus Jansen and Stefan Kratsch and Daniel Marx and Ildiko Schlotter. Bin Packing with Fixed Number of Bins Revisited. To appear in Journal of Computer and System Sciences, Elsevier. Available online: http://dx.doi.org/10.1016/j.jcss.2012.04.004
Pinar Heggernes and Pim van 't Hof and Bart M. P. Jansen and Stefan Kratsch and Yngve Villanger. Parameterized Complexity of Vertex Deletion into Perfect Graph Classes. To appear in Theoretical Computer Science, Elsevier. Available online: http://dx.doi.org/10.1016/j.tcs.2012.03.013.
Stefan Kratsch. Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP. In Algorithmica, Springer, 2012.

Publications in conference proceedings:

Stefan Kratsch and Pascal Schweitzer. Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs. In WG 2012.
Hans L. Bodlaender and Bart M. P. Jansen and Stefan Kratsch. Kernel Bounds for Structural Parameterizations of Pathwidth. In SWAT 2012.
Stefan Kratsch and Marcin Pilipczuk and Ashutosh Rai and Venkatesh Raman. Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. In SWAT 2012.
Robert Bredereck and Jiehua Chen and Sepp Hartung and Stefan Kratsch and Rolf Niedermeier and Ondrej Suchy. A Multivariate Complexity Analysis of Lobbying in Multiple Referenda. In AAAI 2012.
Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Magnus Wahlström. Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. In ICALP 2012.
Marek Cygan and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Magnus Wahlström. Clique Cover and Graph Separation: New Incompressibility Results. In ICALP 2012.
Stefan Kratsch and Magnus Wahlström. Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. In SODA 2012.
Stefan Kratsch. Co-nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-type Problem. In SODA 2012.
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)