Homepage

Stefan Kratsch

News: I have moved to TU Berlin on November 1 2012 where I am now leading a junior research group funded by the Emmy Noether program of DFG (German Research Foundation).

Email: stefan (dot) kratsch (at) tu (minus) berlin (dot) de
Email(2): skratsch (at) mpi (minus) inf (dot) mpg (dot) de
Phone: +49 30 314 25312
Fax: +49 30 314 23516

Research Interests

Parameterized complexity, especially kernelization
Graph problems, constraint satisfaction problems
Computational complexity

Academic Appointments

November 2012 - present:
Junior research group leader at TU Berlin supported by the Emmy Noether program of the German Research Foundation (DFG).
September 2012 - October 2012:
PostDoc at Max-Planck-Institute for Informatics
September 2010 - August 2012:
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)

Publications (dblp)

Publications in refereed journals (dblp):

Stefan Kratsch and Frank Neumann. Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem. In Algorithmica, Springer, 2013.
Danny Hermelin and Chien-Chung Huang and Stefan Kratsch and Magnus Wahlström. Parameterized Two-Player Nash Equilibrium. In Algorithmica, Springer, 2013.
Klaus Jansen and Stefan Kratsch and Daniel Marx and Ildiko Schlotter. Bin Packing with Fixed Number of Bins Revisited. In Journal of Computer and System Sciences, Elsevier, 2013.
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 (see also dblp):

Marek Cygan and Stefan Kratsch and Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings. In STOC 2013.
Stefan Kratsch. On Polynomial Kernels for Sparse Integer Linear Programs. In STACS 2013.
Fedor V. Fomin and Stefan Kratsch and Marcin Pilipczuk and Michal Pilipczuk and Yngve Villanger. Tight bounds for Parameterized Complexity of Cluster Editing. In STACS 2013.
Stefan Kratsch and Magnus Wahlström. Representative Sets and Irrelevant Vertices: New Tools for Kernelization. In FOCS 2012.
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.

Scientific activities

PC member of ISAAC 2013
PC member of FSTTCS 2012
PC member of IPEC 2012